# Final Exam Review

1. Prove using induction: 1 + 3 + 5 +···+ (2n − 1) = n^2
2. Give a big-O estimate for the number of operations (where an operation is an addition or multiplication) used in this segment of an algorithm:

t:=0
for i:=1 to 3
for j:=1 to 4
t:=t+ij

3. Suppose that there are n = 2^k teams in an elimination
tournament, where there are n/2 games in the first round,
with the n/2 = 2^k−1 winners playing in the second round,
and so on. Develop a recurrence relation for the number
of rounds in the tournament.
4.  Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.
5. a) Let f(n) and g(n) be functions from the set of positive integers to the set of real numbers. State the definition of the fact that f(n) is O(g(n)).
b) Use your definition from (a) to prove that 1^2 + 2^2 + ……. + n^2 is O(n^3).

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

### 2 Responses to Final Exam Review

1. Kate Poirier says:

This is a pretty short exam, but this is a nice set of questions. I wasn’t sure the statement for #1 was actually true (I have a bad memory). Luckily, it’s straightforward to check using induction! You should be careful though…you wouldn’t want to try showing this for all non-negative integers, since the left-hand-side doesn’t appear to be defined if n=0; you should indicate clearly that you want to show this is true for all *positive* integers.