CS 4104 Homework 1 (Fall 2009)

1. (30 points) Solve exercise 4 in Chapter 2 (pages 67-68) of "Algorithm Design" by Kleinberg and Tardos. Provide a proof for your solution. There are 21 pairs of functions. You need not compare every pair of functions in your proof. By judicial choice of which functions to compare, the number of function pairs you need to compare is much smaller than 21.
   Notes:
   1. Keep in mind that in order to prove that f(n) is O(g(n)), you must exhibit the constants required by the definition of asymptotic upper bound, and show that the inequality in the definition is satisfied by the functions, given these constants.
   2. Note that g₄(n) is printed before g₃(n) in the textbook.


2. (20 points) Solve exercise 5 in Chapter 2 (page 68) of "Algorithm Design" by Kleinberg and Tardos. If you decide that a statement is true, provide a short proof.


3. (50 points) Solve part (a) of exercise 8 in Chapter 2 (pages 69-70) of "Algorithm Design" by Kleinberg and Tardos. First describe. your algorithm. Next, you must prove its correctness. Finally, you must prove that your algorithm's running time grows slowly than linearly. Separating these three pieces into sections called "Algorithm", "Proof of Correctness", and "Analysis of Running Time" will be helpful. If you like, you may show how you arrived at the algorithm. But this is not necessary. It is enough to describe the algorithm, prove its correctness, and analyse its running time. You need not solve part (b) of the exercise.
   Note: Once you hit upon the right idea, the proof of correctness is rather trivial. The analysis of the running time is a little bit more complicated.