2. (a) Consider the following algorithm.Input: A non-negative integer n.(1) If n % 5 = 0, stop. Otherwise, go to (2).(2) Replace n by n +3, and go back to (1).Prove that this algorithm terminates for every choice of the input n.(b) Consider the following algorithm, in whichf(n) = n – 7n² + 14n – 8.Input: An integer n.(1) If f(n) = 0, stop. Otherwise, go to (2).(2) Replace n by n² % 7 and go back to (1).Prove that this algorithm terminates if and only if n is not a multiple of 7.

As per Bartleby rules, we are answering only one question 2. (a) We are using PYTHON here to…

(a) Consider the following algorithm. Input: A non-negative integer n. (1) If n % 5 = 0, stop. Otherwise, go to (2). (2) Replace n by n + 3, and go back to (1). Prove that this algorithm terminates for every choice of the input n. 2.

(a) Consider the following algorithm. Input: A non-negative integer n. (1) If n % 5 = 0, stop. Otherwise, go to (2). (2) Replace n by n + 3, and go back to (1). Prove that this algorithm terminates for every choice of the input n. 2.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: suppose that n is not 2i for any integer i. How would we change the algorithm so that it handles the…

A: Introduction: Recursive Algorithm Modification: By altering the base case, we can make the recursive…

Q: Prove or disprove "Suppose that m and n are integers. If m > n ≥ 0, then gcd (m, n) = gcd (m − n,…

A: Prove or disprove "Suppose that m and n are integers. If m > n ≥ 0, then gcd (m, n) = gcd (m − n,…

Q: Let m be a randomly chosen non-negative integer having at most n decimal digits, i.e. an integer in…

A: Let m be randomly chosen non-negative integer having at most n digits, i.e.,an integer in the…

Q: The following algorithm is given: int FooBar(c; n): int p = 2 ? ? n result = 1 while (p > 0): result…

A: In this analysis, examined the given function FooBar(c, n) and its time complexity in terms of n.…

Q: Given n integers {a₁, az, ..., an}, let S = a₁ + a2 + + an. Suppose that S is even. Design an…

A: This problem can be solved using dynamic programming approach. We can create a 2D array dp[i][j],…

Q: In the divided and conquer algorithm for computing the maxima set of a given set A of n points in…

A: The question is choose the correct options applicable for the question.

Q: Given a positive integer number n (i.e., n>0), we can use the following algorithm to find the nth…

A: According to the Question below the Solution:Output:

Q: Consider the set of integers. 1. Use a direct proof to show that the sum of two even integers is…

A: 1. Use a direct proof to show that the sum of two even integers is even. Solution: let assume x and…

Q: Solve the following recurrence equations by expanding the formulas (also called the 'iteration…

A: a) solution:-

Q: Let C(n) = 1^3 + 2^3 + 3^3+…+n^3 be the sum of the first n cubes. a. Write a recursive algorithm to…

A: Given Data: Let C(n)=13+23+33+…+n3

Q: You are standing in front of an infinitely long straight fence; that is, the fence extends…

A: Solution is given below :

Q: The following algorithm is given: int foo(int x; y) if x == 0 return y y = 2 · y + x%2 return…

A: Given algorithm include different statements like if condition and functions which include different…

Q: Computer Science solve the following recurrence equation by substitution. assume n is the power of…

A: Here, we are going to solve recurrence relation T(n) = 4T(n/2)+2n, if n>1 using substitution…

Q: Let pn(x) be the probability of selling the house to the highest bidder when there are n people, and…

A: Let pn(x) be the probability of selling the house to the highest bidder when there are n people, and…

Q: To determine a secret integer between 1 and N is your objective. You consistently make guesses for…

A: The question asks for two algorithms that can be used to guess a secret integer between 1 and N.…

Q: The following algorithm construct a sequence of positive whole numbers, which demonstrates the…

A: Actually, algorithm is an step by step process.

Q: Given an n-element array X of integers, Algorithm A executes an On34-time computation for each even…

Q: Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem…

A: A recurrence relation shows a pattern in terms of one or more of its preceding terms, often used to…

Q: Prove that the following algorithmfor computing Fibonacci numbers is correct. function fib(n)…

A: To prove the correctness of the given algorithm for computing Fibonacci numbers, we need to show…

Q: Consider the following problem: given a list of integers N and an individual integer n, is there any…

A: True. There is a semi-decision procedure to determine if there is any element in the list of…

Q: The Fibonacci function f is usually defined as follows. f (0) = 0; ƒ(1) = 1; for every n e N>1, f(n)…

A: Solution: Given, f(0) = 0 f(1) = 1

Q: order Spada numbers are well established in the insurance industry. Formally they are defined by the…

A: It is defined as simply a series of instructions that are followed, step by step, to do something…

Q: For a problem we have come up with three algorithms: A, B, and C. Running time of Algorithm A is…

A: Answer in step 2

Q: Prove or disprove the following statements: 1)Suppose that f(n) = Θ(nlogn) and g(n) = Θ(n2/logn).…

A: 1. The given statement can be prove f(n) = Θ(nlogn) and g(n) = Θ(n2/logn). Then, h(n) = f(n) x g(n)…

Q: Give an example of an algorithm that is O(1), an algorithm that is O(n) and an algorithm that is…

A: Consider an example of array of size n and we can provide examples for all time complexities O(1),…

Q: Mathematical Induction: Binet's formula is a closed form expression for Fibonacci numbers. Prove…

A: Given the question,

Q: Suppose that an algorithm has runtime 20 n3 for n 100, the slowest cases for each n take time 2 n2…

A: The question is on: finding worst-case runtime and average case runtime of the given algorithm.

Q: prem: The difference between any odd int any even integer is odd. pof: Suppose n is any odd integer,…

A: Let's see the solution.

Q: Prove: For all integers n, if n² is odd, then n is odd. Use a proof by contraposition, as in Lemma…

A: Contraposition Method : contraposition is a kind of immediate inference during which a proposition…

Q: Consider the following recursive algorithm, where // denotes integer division: 3//2 = 1, 5//2 = 2,…

A: The worst-case time complexity of an algorithm represents the maximum amount of time it could take…

Q: There are n different sizes of boxes, from 1 to n. There is an unlimited supply of boxes of each…

A: Hi there, Please find your solution below, I hope you would find my solution useful and helpful.…

Q: numerous bouquet combinations, including two 5-rose bouquets (total profit of $70), and a 4-rose…

A: Roses 1 2 3 4 5 Profit $5 $15 $24 $30…

Q: Prove: For all integers n, if n² is odd, then n is odd. Use a proof by contraposition, as in Lemma…

A: For all integers n, if n² is odd, then n is odd. Use a proof by contraposition ?

Q: not handwritten Design a divide and conquer algorithm to solve the following problem in Θ(n log…

A: In this question we need to write an algorithm which finds indices i and j which maximizes the value…

Q: Design and analyze asymptotically a divide-conquer algorithm for the following problem: input: a…

A: Introduction : Algorithm A: Input: s, a string of length n Output: the number of substrings of s…

Q: Suppose that you have two different algorithms for solving a problem. To solve a problem of size n,…

A: Suppose that you have two different algorithms for solving a problem. To solve a problem of size n,…

Q: Find the running time for each of the following algorithms. Show work by finding a table of values…

A: In this question we have to perform the analysis of the running time of Func4(n), which is an…

Q: Prove that the sum of the first n odd positive integers is n2. In other words, show that 1 + 3 + 5 +…

A: To prove that the sum of the first n odd positive integers is n^2, we will use mathematical…

Question

2. (a) Consider the following algorithm.
Input: A non-negative integer n.
(1) If n % 5 = 0, stop. Otherwise, go to (2).
(2) Replace n by n +3, and go back to (1).
Prove that this algorithm terminates for every choice of the input n.
(b) Consider the following algorithm, in which
f(n) = n – 7n² + 14n – 8.
Input: An integer n.
(1) If f(n) = 0, stop. Otherwise, go to (2).
(2) Replace n by n² % 7 and go back to (1).
Prove that this algorithm terminates if and only if n is not a multiple of 7.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1

Code

Code Screeenshot

OUTPUT

Step by step

Solved in 4 steps with 6 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Consider the following algorithm: GeoSum(r, n) Input: Positive real number r and natural number n pn+1 Output: 1. r-1 If (n = 0), Return( 1 ) sum= GeoSum(r, n – 1)+r" Return sum Prove that this algorithm computes the function f(r,n) = " . (HINT: Prove by induc- pn+1 r- tion on n.)
1. Determine the running time of the following algorithm. Write summations to represent loops and solve using bounding. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer. Func1(n) 1 2 3 4 5 6 7 8 9 10 11 S← 0; for i ←n to n² do for j← 1 to i do for k9n to 10n² do for mi to k end end end return (s); end s+s + i- j + k −m;
Given is a strictly increasing function, f(x). Strictly increasing meaning: f(x)< f(x+1). (Refer to the example graph of functions for a visualization.) Now, define an algorithm that finds the smallest positive integer, n, at which the function, f(n), becomes positive. The things left to do is to: Describe the algorithm you came up with and make it O(log n).
Find the running time for each of the following algorithms. Show work by finding a table of values for each while loop, writing the summations, then solving. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer. b) Func3(n) 1 2 3 4 5 6 7 8 9 10 11 S← 0; i+n; while (i 8) do s+ s + i - j; j← lj/⁹]; end i + 4 x i; end return (s);
Prove by Induction that for all integers n ≥ 1, n < n2 + 1 .Yes this problem is silly, but still do it by induction! Prove by Induction that for all integers n ≥ 3, 2n < n2 .
An integer n is called k-perfect if u(n) =kn. Note that a perfect number is 2-perfect. Showthat 120 = 23 • 3 · 5 is 3-perfect.
Note: For all integers k,n it is true that kn, k+n, and k-n are integers. An integer k is even if and only if there exists an integer r such that k=2r. An integer k is odd if and only if there exists an integer r such that k=2r+1. For every integer k it is true that if k is even then k is not odd. For every integer k it is true that if k is odd then k is not even. For every integer k it is true that if k is not even then k is odd. For every integer k it is true that if k is not odd then k is even. If P then Q means the same thing as P → Q (P implies Q). 3. Consider the argument form pvr .. p→r Is this argument form valid? Prove that your answer is correct. 4. Prove that for every integer d, if d³ is odd then d is odd.
Let n be an integer, use the definition of even to prove that 18n + 2 is even. 18n + 2 = Since X is an integer, is also an integer. Since 18n +2 equals 2 times an integer, 18n + 2 is even.
Below is pseudocode representing the Compute-Opt algorithm: Compute-Opt(j): If j = 0 then Return 0 Else Return max(vj+Compute-Opt(p(j)), Compute-Opt(j − 1)) Endif Memoization of this algorithm does what to its running time? Group of answer choices It reduces the running time from exponential to linear. It reduces the running time from O(n2) to O(n). It reduces the running time from exponential to O(n log n). It doesn't significantly reduce the running time, but it enables the algorithm to utilize less space.
16. Write an efficient algorithm for evaluating n =ΣΠΑ i=j=1 u=
2- Prove that the following statements are true (7) or false (F). (let log n = log2 n). You must define first what you are trying to prove using the limit definition. a) n³/log n = O(n), for any integer constant 2 ≤ k ≤ 3. E b) n+nlog n = (n log n), for any positive integer constant k. c) n log n² = Q(), for any integer constant k> 0.
Consider the following recursive algorithm, where // denotes integer division: 3//2 = 1, 5//2 = 2, etc. F(n):if n <= 1: returnF(n//2)for i from 0 to n for j from 0 to n//2 print(i+j) Let function T(n) denote the running time of this algorithm. Derive T(n) and prove its worst case timecomplexity