Problems from N.R. Wagner for the CS3343 Final Exam, Spring 2004
1. (a) Use induction to prove the following matrix identity:
n
| 0 1 | | F(n-1) F(n) |
| | = | |, where n >= 1
| 1 1 | | F(n) F(n+1) |
Here F(n) is the nth Fibonacci Number:
F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2), for n >= 2.
(So F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, ....)
The above formula involves matrices, and on the left,
we are multiplying the matrix times itself n times.
For full credit you MUST clearly indicate what you are
assuming and what you are proving. It is not enough just
to write some formulas.
(b) In class, we discussed two efficient algorithms for raising
a number to a power. If n is the exponent, what is the
Big-Theta performance of either of these raise-to-a-power
algorithms in terms of n.
(c) In class, we discussed how the formula in part (a) gave a
more efficient way to calculate F(n), the nth Fibonacci Number.
Say briefly how you can efficiently use the formula to
calculate F(n). Give the Big-Theta performance of this
algorithm.
2. Consider the following algorithm that we studied in class:
A = array with n elements, indexed by 0 to n-1 inclusive;
void randomize(type[] A) {
for (int i = 0; i < n-1; i++) {
int r = randomInt(i, n-1); // i to n-1 inclusive
interchange(A[i], A[r]); // possibly i == r
}
}
(Here randomInt(a, b) returns a true random int r,
satisfying a <= r <= b such that each of the integers
between a and b (inclusive) is equally likely to occur.)
(a) Trace through the execution of this function, showing
the result after each loop iteration, using as input the
array of integers A = {6, 7, 8, 9}, so that n == 4,
and "type" is "int". Assume the function randomInt
returns 2, 1, and 3 the three times it is called.
(b) Say in detail what happens if the loop is written
for (int i = 0; i < n; i++)
with "n" instead of "n-1". (You must say much more
than just that "there is another loop iteration.")
(c) What does this function do, and what did we use it
for in the course?
3. The Bell Numbers B(n,k) satisfy the recursive definition:
B(1, 1) = 1
B(n, n) = B(n-1, 1), for any n > 1
B(n, k) = B(n-1, k) + B(n, k+1), for any k >= 1 and n > k
(a) At first glance it might seem as if this formula will not
work, because the third part of the formula involves n and k+1
on the right to calculate n and k on the left. Trace through
the definition by hand to see how the value for B(3, 1) is
obtained. (Be careful!)
(b) Write a simple recursive function in C, C++, or Java
to calculate any Bell number.
(c) Describe in general how the MEMOIZATION technique would
be used to rewrite the function in part (b) (without actually
rewriting it). Why would one want to rewrite it in this way?
What general algorithm design technique does this represent
(using a different word or phrase than "memoization")?
======================================================================
ANSWERS:
1. (a) For a basis, we assert that the formula is true for n == 1:
This is obvious, since on the left and the right we have
the same matrix:
| 0 1 |
| |
| 1 1 |
Now ASSUME that the formula is true for any n >= 1, that is
assume that
n
| 0 1 | | F(n-1) F(n) |
| | = | |, where n >= 1
| 1 1 | | F(n) F(n+1) |
We need TO PROVE the corresponding formula for n+1:
n+1
| 0 1 | | F((n+1)-1) F(n+1) | | F(n) F(n+1) |
| | = | | = | |
| 1 1 | | F(n+1) F((n+1)+1)| | F(n+1) F(n+2) |
But
n+1 n
| 0 1 | | 0 1 | | 0 1 |
| | = | | * | | = (by induction
| 1 1 | | 1 1 | | 1 1 | assumption)
| F(n-1) F(n) | | 0 1 |
| | * | | = (multiplying out)
| F(n) F(n+1) | | 1 1 |
| F(n-1)*0 + F(n)*1 F(n-1)*1 + F(n)*1 |
| | = (simplify)
| F(n)*0 + F(n+1)*1 F(n)*1 + F(n+1)*1 |
| F(n) F(n-1) + F(n) |
| | = (properties of Fibonacci numbers)
| F(n+1) F(n) + F(n+1) |
| F(n) F(n+1) |
| |, which is what was to be proved.
| F(n+1) F(n+2) |
This completes the proof by induction.
[Note: Just giving the final calculation is NOT SUFFICIENT.]
(b) Both of the raise-to-a-power algorithms run in time
Big-Theta(log n). This is because their loops iterate through
the bits of the binary expansion of n, and there are
log-base2(n) of these bits.
(c) Using the formula in (a) and the efficient raise-to-a-power
algorithm to multiply the matrices, it is obvious that this is
a Big-Theta(log n) algorithm to calculate F(n).
2. (a) Here are the results of the three loop iterations:
Initially A = {6, 7, 8, 9}
i = 0:
randomInt(0,3) == 2 (by assumption)
interchange(A[0], A[2])
A == {8, 7, 6, 9}
i = 1:
randomInt(1,3) == 1 (by assumption)
interchange(A[1], A[1])
A == {8, 7, 6, 9} (no change)
i = 2:
randomInt(2,3) == 3 (by assumption)
interchange(A[2], A[3])
A == {8, 7, 9, 6}
Final result: A == {8, 7, 9, 6}
(b) There is a additional loop iteration with i == n-1
In this case, there is a call
r = randomInt(n-1, n-1), which must return r == n-1
Then the code interchange(A[n-1], A[n-1]) will have no effect.
Thus this extra loop iteration has no effect on the result of
the algorithm, but only makes it run slightly slower.
(c) This function randomizes the order of elements in the array A.
We used it in class for one version of a randomized Quicksort
algorithm. Using randomized input makes the worst-case
bad performance of quicksort extremely unlikely.
3. (a) B(3, 1) = B(2, 1) + B(3, 2)
= B(1, 1) + B(2, 2) + B(2, 2) + B(3, 3)
= 1 + B(1, 1) + B(1, 1) + B(2, 1)
= 1 + 1 + 1 + B(1, 1) + B(2, 2)
= 1 + 1 + 1 + 1 + B(1, 1)
= 1 + 1 + 1 + 1 + 1 = 5
(b)
int B(int n, int k) {
if (n == 1 && k == 1) return 1;
if (n == k) return B(n-1, 1);
return B(n-1, k) + B(n, k+1);
}
(c)
Using the memoization technique, you create an array,
call it b[][], that will hold intermediate results of calculating
Bell numbers. Initialize b to all -1 values (say).
During the course of calculating the value B(n,k),
you first look up in b[n][k] to see if the array entry
is not -1. If so, just return this value as the answer.
Then as you call B(n-1,k) and get an answer, store
this answer into b[n-1][k], and similarly for B(n, k+1).
This illustrates a simple form of DYNAMIC PROGRMMING.