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.
Oooohhh, I like #2!