CS 5114 Homework 1 (Spring 2009)

Assigned on Thursday, January 29, 2009. Hardcopy due at the beginning of class on Thursday, February 5, 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 functions pairs you need to compare is much smaller than 21. Note that g4(n) is printed before g3(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. After describing your algorithm, you must prove that its running time grows slowly than linearly. You need not solve part (b) of the exercise.