CS 5114 Homework 1 (Spring 2013)

1. (25 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 g₄(n) is printed before g₃(n) in the textbook.
2. (15 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. (45 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. You do not need to describe the train of thought that led to your algorithm.
4. (15 points). Describe an algorithm to merge k sorted lists into one sorted list. Each sorted list has n integers. Neither k nor n is a constant. Analyze the running time of your algorithm. You will get partial credit if your algorithm is not fast "enough."