CS 325 Homework #3

CS 325
Homework #3
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 n
th Fibonacci number and let fn−1 be the (n − 1)st Fibonacci number.
(a) Use Euclid’s algorithm to compute GCD(233, 144).
(b) What is the numerical value of gcd(fn, fn−1)?
(c) Write down a difference equation for the number of recursive calls Euclid’s algorithm makes in computing GCD(fn, fn−1).
(d) Solve your difference equation from (c).
3. Solve, the following difference equation initial value problems.
If the problem is nonnegative, find 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 satisfies
T(n) = T(n − 1) + T(n − 2) + T(n − 3)
use induction to show that T(n) = Θ(λ
n
0
) where λ
3
0 = λ
2
0 + λ0 + 1.
(HINT: For the base caseS use the reasonable assumption that
T(3) 0, T(2) 0, T(1) 0. )
5. An AVL tree is a binary tree in which at each vertex the heights of the right and left
subtrees of that vertex differ 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 difference equations for the maximum
and the minimum number of vertices in an AVL tree.
Find appropriate initial conditions for these difference 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. )
6. After listening to Fibonacci’s argument that Arabic numbers are superior to Roman numerals, 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 puff 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.