# 2002 F

*216,210*pages on

this wiki

## Ad blocker interference detected!

### Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

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.