1. (10%) Describe an algorithm that, given n integers in the range 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.

2. (15%) Let G=(V,E) be a weighted directed graph, where V={1, 2, ..., n} is the vertex set and E is the edge set of G, respectively. Let W be the weighted adjacent matrix of G, in which stores the length of the edge between vertex i and vertex j (=0 if i=j and =∞ if (i,j)∉E)

- (a) (7%) Let be the weight of a shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2, ..., k}, k≥0 is an integer. Write a recurrence of . Justify your answer.
- (b) (8%) Based upon the recurrence , design an algorithm to compute the shortest distance between every pair of vertices i and j. What is the time complexity of your algorithm?

3. (15%) The following is Dijkstra's single-source shortest paths algorithm.

- DIJKSTRA(G=(V,E),w,s) /* G is a weighted graph with weight matrix w. s is the source vertex. */
- 1. for each vertex v∈V do d[v]←∞
- 2. d[s]=0; S←∅
- 3. Q←V /* Build a priority queue Q which contains all vertices of G. */
- 4. while Q≠∅
- 5. u←Extract-Min(Q) /* Extract-Min removes and returns the one with the minimum key value in Q. */
- 6. S←S∪{u}
- 7. for each vertex v∈Adj[u] do /* Adj[u] denotes the adjacent list of u. */
- 8. if d[v]>d[u]+w(u,v) then Decrease-Key(Q,V,d[u]+w(u,v)) /* Decrease-Key assigns v a smaller, new key value d[u]+w(u,v). */

- (a) (5%) Suggest an implementation of the priority queue Q such that Step 3 performs in O(|V|) time and each call to Extracn-Min or Decrease-Key performs in O(log|V|) time. Justify your answer.
- (b) (10%) What is the time complexity of the algorithm DIJKSTRA in terms of V and E while Q is implemented as your suggestion. Justify your answer.

4. (10%)

- (a) (3%) Let g(n) be a function. Give the definition of O(g(n)).
- (b) (3%) Is =O()? Prove it.
- (c) (4%) Is =O()? Prove it.

5. (8%) Prove that 2n-1 comparisons are necessary in the worst case to merge two sorted lists containing n elements each.

6. (8%) A set S of nodes in V is called a node cover of G if every edge is incident to some node in S. Give a nondeterministic polynomial algorithm for the node cover decision problem. Your algorithm should not try all subsets of V.

7. (9%) Determine whether each of the following statements is correct or not, and justify your answer.

- (a) Any NP-hard problem can be solved in polynomial time if there is an algorithm that can solve the satisfiability problem in polynomial time.
- (b) Any NP-complete problem can be solved by a polynomial time deterministic algorithm in average if and only if NP=P is proved.
- (c) The clause-monotone satisfiability problem is NP-complete, where a formula is called monotone if each clause of the formula contains either only positive variables or only negative variables.

8. (15%)

- (a) (5%) Show how to multiply two linear polynomials ax+b and cx+d using only three multiplications. (Hint: one of the multiplications is (a+b)(c+d).)
- (b) (10%) Show that two n-bit integers can be multiplied in O() steps, where each step operates on at most a constant number of 1-bit values.

9. (10%) Give an O(n)-time algorithm to locate the -th largest element for a given n-element set. Justify the time complexity of your algorithm.