1. (10%)

- (a) (4%) Describe the k-coloring problem, where k≥1 is an integer.
- (b) (6%) Prove that 3-coloring ∝ k-coloring for any k>3.

2. (10%) Let , i=1, 2, ..., m, be m sorted lists. Each , 1≤i≤m, consists of elements.

- (a) (5%) Give an algorithm to construct an optimal 2-way merge tree for , i=1, 2, ..., m.
- (b) (5%) What's the time complexity of your algorithm?

3. (14%)

- (a) (7%) Let f(n) and g(n) be asymptotically nonnegative functions. Using the definition of Θ-notation, prove that max(f(n),g(n))=Θ(4f(n)+2g(n)).
- (b) (7%) Find an upper bound on the recurrence T(n)=T()+1 by using the substitution method. (You may assume that T(1)=1.)

4. (10%)

- (a) (5%) Give a clear description of the algorithm for quick sort.
- (b) (5%) What is a randomized algorithm? What is the advantage offered by a randomized version of quick sort?

5. (10%) Describe an algorithm that, given n integers in the range of 1 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a..b] in O(1) time. Your preprocessing algorithm should perform in O(n+k) time.

6. (10%)

- (a) (4%) Give a clear description of the algorithm for radix sort.
- (b) (6%) Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

7. (10%) Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of length , measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Out criterion of "neatness" is as follows. If a given line contains words i through j and we leave exactly one space between words, the number of extra space characters at the end of the line is M-j+i-. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space character at the ends of lines.

- (a) (5%) Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. (Please define your notation clearly.)
- (b) Analyze the running time and space requirements of your algorithms (interms of big-O notation).

8. (13%)

- (a) (6%) Describe Dijkstra's algorithm that solves the single-source shortest-[aths problem on a weighted, directed graph G=(V,E), in which all edge weights are nonnegative.
- (b) How can we implement Dijkstra's algorithm in O(|V|log|V|+|E|) time.

9. (13%)

- (a) (6%) Design an approximation algorithm for the Euclidean traveling-salesman problem, using the minimum-spanning-tree alorithm. Do NOT explain the minimum-spanning-tree algorithm. Just explain how you use its results to build your approximation algorithm.
- (b) (7%)Prove that the above approximation algorithm has a ratio bound of 2.