Final Exam Review

1. Use pseudocode to describe an algorithm that takes a list of n integers a1, a2, . . ., an and finds the number of integers which are greater than 5 in the list.
2. Use pseudocode to descibe an algorithm to find the largest and second largest elements in a list of integers.
3. Give a big-O estimate for the number of operations (where an operation is an addition or a multiplcation) used in this segment of an algorithm:
t:= 0
for i:= 1 to 3
for j:= 1 to 4
t:= t+ij
Explain your answer.
4. Show that f(n) = x2+x+1 is O(x2)
5. Solve: an = 4an-1-4an-2; a0 = 1 a1 = 1 (recuurence relation)
6. Solve: an = 5an-1 + 6an-2; a0=7 a­n= 16 (reccurence relation)
7. Suppose f(n)= f(n/3)+1 where n is a positive integer divisible by 3 and f(1) = 1. Find f(3), f(9), f(27), f(2187).
8. Find a closed form for the generating function for each of these sequences.
a) 0, 0, 0, 1, 1, 1, 1, 1, 1, …
b) 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, …
c) 1, 1, 0, 1, 1, 1, 1, 1, 1, 1…
9. Solve using generating functions: ak=3ak-1+2; a0=1
10. Prove: 1 + 3 + 5 +···+ (2n − 1) = n2 (induction)
11. Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 20 = 1, 21 = 2, 22 = 4, and so on. [Hint: For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.]