Question

The following is Algorithm 8 from §5.4. Note that it uses the following definition of the...

The following is Algorithm 8 from §5.4. Note that it uses the following definition of the fibonacci sequence: fn = fn−1 + fn−2, f1 = 1, f0 = 0.

procedure iterative fibonacci(n: nonnegative integer)

if n = 0 then return 0

else

x := 0 y := 1

for i := 1 to n − 1 do

z := x + y x := y y := z

end for

return y

end if

end procedure

Prove this algorithm is correct.

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

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
Homework 6 Problem 2 Translate the third of the following three algorithms to C++. Write a...
Homework 6 Problem 2 Translate the third of the following three algorithms to C++. Write a program to test the function. The first few Fibonacci numbers are 1,1,2,3,5,8,13,21,34,55,89,144,… Fibonacci(n)    f1 = 0    f2 = 1    fib = 0    while n > 0      f1 = f2      f2 = fib      fib = f1 + f2      n = n – 1    end while    return fib end fibonacci fibonacci(n) if n < 1 then...
Prove the following identities. (a) F1 +F3 +F5 +...+F2n−1 = F2n. (b) F0 −F1 +F2 −F3...
Prove the following identities. (a) F1 +F3 +F5 +...+F2n−1 = F2n. (b) F0 −F1 +F2 −F3 +...−F2n−1 +F2n = F2n−1 −1. (c) F02 +F12 +F2 +...+Fn2 = Fn ·Fn+1. (d) Fn−1Fn+1 − Fn2 = (−1)n. Discrete math about Fibonacci numbers
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
Translate the following C function into MIPS assembly code. Note that function f1 is defined somewhere...
Translate the following C function into MIPS assembly code. Note that function f1 is defined somewhere else. int f2(int x, int y) { int i, z = 0; for (i = x; i <= y; i++) z = z + f1(i, 5); return z; }
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci...
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … The sequence Fn of Fibonacci numbers is defined by the recurrence relation: Fn = Fn-1 + Fn with seed values F1 = 1 F2 = 1 For more information on...
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in...
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in the deck and they are each represented by an element in {X, Y, Z}. [Bonus marks if you use the deck {W, X, Y, Z}] Algorithm Shuffle --------------------------------------------------- deck := [X,Y,Z] for i from 0 to 2 do j := RANDOM(i) swap values of deck[i] and deck[j] end for return deck --------------------------------------------------- For each of the following definitions of RANDOM(i), compute the probability distribution...
Consider the following recursive algorithm for computing the sum of the first ? cubes: ? (?)...
Consider the following recursive algorithm for computing the sum of the first ? cubes: ? (?) = 13 + 23 + ⋯+ ? 3 . Algorithm S(n) //Input: A positive integer n //Output: The sum of the first n cubes if n = 1 return 1 else return S(n-1) + n * n * n
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.
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....
Determine the order of complexity for the following algorithm: function(int n) { int l, u, m;...
Determine the order of complexity for the following algorithm: function(int n) { int l, u, m;    l=0; u= n-1;    while (l<u) {        m= (l+u)/2;        if (a[m] < x) l= m+1;        else if (a[m] >x) u=m-1;            else return “found”    }    return (“not found”); }
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT