HOMEWORK 2

Background: Ch. 2.1, 4.

Due September 17th:

• 2.1: Derive normal-form rules (like those for multiplication and addition) for (a) minimization and (b) squaring.

• 2.2: Give a proof for the solution of T(1) = 1, $T(n) = n + T(\lfloor n/2 \rfloor)$ (not using Master Method).
• 2.3: CLR Exercise 4.1-5 (pg 57).
• 2.4: CLR Exercise 4.3-1 (pg 64).
• 2.5: The quicksort vs. insertion sort comparison we ran was on random lists. Rerun the experiment on sorted lists and plot the data. (The UTAs will help make the code available.) [Delayed a week.]

• 2.6: Are there a pair of real constants $k<\infty$ and $\epsilon\gt$such that $n^\epsilon = o(\log^k n)$? If there is, what are they? If there isn't, why not?
• 2.7: CLR Problem 4-1 (pg 72), CLR Problem 4-4 (pg 73-74). [Extra Credit. It's good practice!]