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
Explain your answer.
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 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.
Pingback: OpenLab Workshop for Opening Gateways Fellows | 2018-2019 Opening Gateways Faculty Seminar