HOMEWORK 1

Background material: Ch. 1, 29.4.2, 2.1, 2.2, 4.1.

Due September 10th:

• 1.1: Send me (mlittman@cs.duke.edu ) your email address (right away).
• 1.2: Multiply $503 \times 447$ using the Russian Peasant's Algorithm.
• 1.3: For Naive multiplication, carry out algorithm development Step 2.
• 1.4: (a) Write a recursive algorithm [Step 1] for computing a^b (where both a and b are positive integers). (b) Prove that it is correct [Step 2]. (c) Analyze the number of recursive calls it makes [Step 3] (it should be logarithmic). You can assume you have built-in (unit-time) multiplication and bit shifting, but not exponentiation or general division.

• 1.5: Demonstrate that $100 \log n = O(\sqrt{n})$ by drawing the appropriate graph. You might use ``gnuplot'' to do this by plotting both of these functions and showing which is bigger.

• 1.6: Prove by induction that $T(n) = 2^{1+\lfloor\log(n)\rfloor}-1$, where T(1) = 1 and $T(n) = 1+2 T(\lfloor n/2 \rfloor)$. You may use the fact that $\lfloor \log(\lfloor n/2 \rfloor)\rfloor = \lfloor \log(n/2)\rfloor$.
• 1.7: CLR Exercise 2.1-2 (pg 31).
• 1.8: CLR Problem 2-6 (pg 40). [Extra Credit, but it's very cool.]