Description
1) Select a data structure that you have seen previously, and discuss its strengths and
limitations. [CLRS 1.1-3]
10 points
2) Suppose we are comparing implementations of insertion sort and merge sort on the
same machine. For inputs of size n, insertion sort runs in 8π
2
steps, while merge sort
runs in 64π lg π steps. For which values of n does insertion sort beat merge sort? [CLRS
1.2-2]
10 points
3) Let πΉπ
represents the i-th Fibonacci number (πΉ0 = πΉ1 = 1). Prove that for all values of
π β₯ 3, the following equation is true using induction:
β πΉπ
πβ2
π=1
= πΉπ β 2
15 points
4) Prove that the following equation is correct for all values of π β₯ 1:
β(2π β 1)
π
π=1
= π
2
15 points