CS 5114 Homework 1 (Spring 2009)
Assigned on Thursday, January 29, 2009. Hardcopy due at the
beginning of class on Thursday, February 5, 2009.
- (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.
- (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.
- (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.