Homework 1 – CPSC 4100-01 solution

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