CS 5114 Homework 1 (Spring 2013)

Assigned on Tuesday, January 29, 2013. Hardcopy due at the beginning of class on Tuesday, February 5, 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 g4(n) is printed before g3(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."