Chapter 1: Warm-up Exercises

Recursion

Binary Search, Book page 13, # 5, 6, 7, 8, 12

Induction

Book page 49, # 2

Here they are in case you do not have the book.

Analysis of Recursive Programs

These provide examples of how timing of recursive programs and induction work together. Do these after we have worked on the timing of algorithms (unless you feel confident from past experience).

Exercise 9.2 of Aho, Hopcroft, and Ullman. "Solve" means "guess a solution and prove it is correct using induction." Assume that n is a power of 2. You may also note the following hints for the respective parts:

(a) The solution contains a term cn^{log₂ 3}
(b) The solution contains a term cn^{log₂ 3}
(c) The solution contains a term cn³log₂n