1. How many times is [ computation ] executed in the following nested loop program:
for i = 1 to 2n 1 by step 2
for j = 1 to i by step 1
[ computation ]
2. Let fn be the nth Fibonacci number and let fn 1 be the (n 1)st Fibonacci number.
Use Euclid’s algorithm to compute GCD(233, 144).
What is the numerical value of gcd(fn; fn 1)?
Write down a di erence equation for the number of recursive calls Euclid’s algo-rithm makes in computing GCD(fn; fn 1):
Solve your di erence equation from (c).
Solve, the following di erence equation initial value problems.
If the problem is nonnegative, nd the \Big Oh" order of the solution and compare it to the \Big Oh" order predicted in the Notes (Ch. 9).
Use one of the mathematical computation packages to solve these DE’s and compare the package’s solution to your solution.
(a) xn = 3xn
1
x0 = 1
(b) xn = 2xn
1
1
x0
= 0
(c) xn = 2xn
1
1
x0
= 1
(d) xn = 5xn
1
4n + 1
x0 = 1
(e) xn = xn 1 + 2 n + 1
x0 = 1
(f) xn = 2xn
1 + 3n
x0
= 7
(g) xn = 2xn
1 + 2n
x0
= 7
4. If the running time for an algorithm satis es
T (n) = T (n 1) + T (n 2) + T (n 3)
use induction to show that T (n) = ( n0) where 30 = 20 + 0 + 1. (HINT: For the base caseS use the reasonable assumption that T(3) 0, T(2) 0, T(1) 0. )
An AVL tree is a binary tree in which at each vertex the heights of the right and left subtrees of that vertex di er by at most 1.
If the AVL tree is of height h what is the maximum possible number of vertices in the tree?
What is the minimum number of vertices? Derive di erence equations for the maximum and the minimum number of vertices in an AVL tree.
Find appropriate initial conditions for these di erence equations.
Solve both these initial value problems and thus obtain bounds on the number of vertices in an AVL tree of height h.
( HINT : Thinking of Fibonacci might help. )
After listening to Fibonacci’s argument that Arabic numbers are superior to Roman nu-merals, Ogh the caveman claimed that his method of representing numbers as notches on a stick was much better because he could add by just putting two sticks together. Then, in a pu of smoke, the ghost of Al Gore appeared and lectured that while Ogh’s method might seem green (as green as a twig), in fact computing Fibonacci numbers using Ogh’s method would be an ecological disaster and would even be slow.
Please explain Al Gore’s claim in terms of the time and space used by Ogh’s algorithm compared to the time and space used by Fibonacci’s algorithm.
