# CS 4104 Homework 1 (Fall 2009)

**Assigned on Monday, August 31, 2009. Hardcopy due at the
beginning of class on Monday, September 7, 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 function pairs you need to compare is much
smaller than 21.

*Notes:*
- 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.
- Note that g
_{4}(n) is printed before
g_{3}(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. 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.