Question

Give a recursive algorithm to solve the following recursive function.    f(0) = 0;    f(1)...

  1. Give a recursive algorithm to solve the following recursive function.

   f(0) = 0;

   f(1) = 1;

f(2) = 4;

f(n) = 2 f(n-1) - f(n-2) + 2; n > 2

  1. Solve f(n) as a function of n using the methodology used in class for Homogenous Equations. Must solve for the constants as well as the initial conditions are given.
Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

A recursive algorithm would look like this and you can now implement it in any desirable language :-

function (n)
  if n == 0
    return 0
  elif n == 1
    return 1
  elif n == 2
    return 4
  else:
    return 2 + 2function(n-1) - function(n-2)

if you have any doubt you can ask in a comment section.Thums up the ans

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider the following function : F 1 = 2, F n = (F n-1 ) 2...
Consider the following function : F 1 = 2, F n = (F n-1 ) 2 , n ≥ 2 i. What is the complexity of the algorithm that computes F n using the recursive definition given above. ii. Describe a more efficient algorithm to calculate F n and give its running time.
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic...
a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic operation? How many times is the algorithm’s basic operation executed? b. Using an = a*an-1 (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed. c. Using an = a*(a(n-1)/2) 2 (n is odd integer) and an =...
Determine if each of the following recursive definition is a valid recursive definition of a function...
Determine if each of the following recursive definition is a valid recursive definition of a function f from a set of non-negative integers. If f is well defined, find a formula for f(n) where n is non-negative and prove that your formula is valid. f(0) = 1, f(n) = -f(n-1) + 1 for n ≥ 1 f(0) = 0, f(1) = 1, f(n) = 2f(n-1) +1 for n ≥ 1 f(0) =0, f(n) = 2f(n-1) + 2 for n ≥...
Solve f(n) as a function of n using the homogeneous equation and given the conditions below:...
Solve f(n) as a function of n using the homogeneous equation and given the conditions below: f(0) = 0;    f(1) = 1; f(2) = 4; f(n) = 2 f(n-1) - f(n-2) + 2; n > 2
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n...
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n 1)What does this algorithm compute? 2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n ==...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n == 0)    return 0; else    return n * f(n - 1); } A. 120 B. 60 C. 1 D. 0 10 points    QUESTION 2 Which of the following statements could describe the general (recursive) case of a recursive algorithm? In the following recursive function, which line(s) represent the general (recursive) case? void PrintIt(int n ) // line 1 { // line 2...
Question 4: The function f : {0,1,2,...} → R is defined byf(0) = 7, f(n) =...
Question 4: The function f : {0,1,2,...} → R is defined byf(0) = 7, f(n) = 5·f(n−1)+12n2 −30n+15 ifn≥1.• Prove that for every integer n ≥ 0, f(n)=7·5n −3n2. Question 5: Consider the following recursive algorithm, which takes as input an integer n ≥ 1 that is a power of two: Algorithm Mystery(n): if n = 1 then return 1 else x = Mystery(n/2); return n + xendif • Determine the output of algorithm Mystery(n) as a function of n....
a) Give a recursive algorithm for finding the max of a finite set of integers, making...
a) Give a recursive algorithm for finding the max of a finite set of integers, making use of the fact that the max of n integers is the larger of the last integer in the list and the max of the first n-1 integers in the list. Procedure power(x,n): If (n=0): return 1 Else: return power(x,n-1) · x b) Use induction to prove your algorithm is correct
Consider the following recursive algorithm. Algorithm Mystery(n) if n=1 then Execute Task A; // Requires Θ(1)...
Consider the following recursive algorithm. Algorithm Mystery(n) if n=1 then Execute Task A; // Requires Θ(1) operations else Mystery(n/3); Mystery(n/3); Mystery(n/3); Execute Task B;  //Requires 2n operations end if Let C(n) be the complexity of Mystery(n). Use the method of backward substitution to determine C(n) in three steps. a) Write the recurrence relation for C(n) including the initial condition. b) Write at least two substitution steps for C(n) and identify the pattern. c) Determine the complexity class of the algorithm in...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT