# Final Exam Review

1)List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using

a) linear search.                                                                            b) binary search.

2)Show that xlog(x) is O(x^2) but that x^2 is not O(xlog(x)).

3)Construct a complete binary tree of height 4 and a complete 3-ary tree of height 3.

4) Using alphabetical order, construct a binary search tree for the words in the sentence “The quick brown fox jumps over the lazy dog.”

5) Solve these recurrence relations together with the initial conditions given:

a) an = 6an−1 − 8an−2 for n ≥2, a0 =4, a1 =10

b) an+2 =− 4an+1 + 5an for n ≥0, a0 =2, a1 =8

6) Suppose that f(n) = f(n/5)+3n^2 when n is a positive integer divisible by 5, and f(1) =4. Find               a) f(5)                                       b) f(125)                                      c) f(3125)

7)For each of these generating functions, provide a closed formula for the sequence it determines.

a) x^2 +3x +7+(1/(1−x^2))                                             b) [(x^4)/(1−x^4))]−x^3 −x^2 −x −1

8)Use induction to prove that 12 +32 +52 +···+(2n+1)2 = (n+1)(2n+1)(2n+3)/3 whenever n is a nonnegative integer.

This entry was posted in Final Exam Review. Bookmark the permalink.

### 1 Response to Final Exam Review

1. Kate Poirier says:

Oooohhh, I like #2!