a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based...

a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based on the formula 3n = 3n−1 + 3n−1 + 3n−1 b. Set up a recurrence relation for the number of additions made by the algorithm and solve it. c. Draw a tree of recursive calls for this algorithm and count the number of calls made by the algorithm. d. Is it a good algorithm for solving this problem?

Expert Solution

venereology answered 2 years ago

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i...

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i ← 1 to n do S ← S + i * i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try...

For any nonnegative integer n, let Y1 < Y2 < · · · < Y2n+1 be...

For any nonnegative integer n, let Y1 < Y2 < · · · < Y2n+1 be the ordered statistics of 2n + 1 independent observations from the uniform distribution on [−2, 2]. (i) Find the p.d.f. for Y1 and the Y2n+1. (ii) Calculate E(Yn+1). Use your intuition to justify your answer.

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based...

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based on the fact that xy = 2(x · (y/2)) when y is even and xy = 2(x · ⌊y/2⌋) + x when y is odd, together with the initial condition xy = 0 when y = 0.

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) =...

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) = 12 +22 +32 +...+n2 . Algorithm S(n) //Input: A positive integer n //Output: The sum of the first n squares if n = 1 return 1 else return S(n − 1) + n* n a. Set up and solve a recurrence relation for the number of times the algorithm’s basic operation is executed. b. How does this algorithm compare with the straightforward non-recursive algorithm...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

3. Consider the following recursive algorithm for computing the sum of the following series: S(n) =...

3. Consider the following recursive algorithm for computing the sum of the following series: S(n) = 1/1! + 2/2! + . . . + n/n!. ALGORITHM S (n) //Input: A positive integer n // Procedure: fact(n) returns the factorial of the number passed as parameter //Output: The sum of the series: S(n) = 1/1! + 2/2! + . . . + n/n! if n = 1 return 1 else return S(n − 1) + n/fact(n) Set up and solve a...

Let A be an integer array of length n. Design a divide and conquer algorithm (description...

Let A be an integer array of length n. Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array. If there are several such elements, your algorithm must return the index of the rightmost element. For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.

1. Prove or Disprove: If n is a nonnegative integer, then 5 | (24n + 39n)

1. Prove or Disprove: If n is a nonnegative integer, then 5 | (2*4n + 3*9n)

Sample Execution : Recursive Euclidean Algorithm to calculate GCD Type a positive integer for...

Sample Execution : ** Recursive Euclidean Algorithm to calculate GCD ** Type a positive integer for A: -2 Sorry, you must enter a positive integer (>0). Please try again. ** Recursive Euclidean Algorithm to calculate GCD ** Type a positive integer for A: 35 Type a positive integer for B: 63 The GCD is 7 Write a MIPS assembly program that prompts the user for 2 positive integers (>0). Then it uses the Recursive Euclidean Algorithm to calculate GCD (the...

Develop a recursive algorithm that multiply two integer numbers x and y, where x is an...

Develop a recursive algorithm that multiply two integer numbers x and y, where x is an m-bit number and y is an n-bit number (10 points), and analyze the time complexity of this algorithm (10 points).

Question