# 1998 S

215,758pages 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%) 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 $w_{i,j}$ stores the length of the edge between vertex i and vertex j ($w_{i,j}$=0 if i=j and $w_{i,j}$=∞ if (i,j)∉E)

(a) (7%) Let $d_{i,j}^{(k)}$ 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 $d_{i,j}^{(k)}$. Justify your answer.
(b) (8%) Based upon the recurrence $d_{i,j}^{(k)}$, 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 $2^{n+1}$=O($2^n$)? Prove it.
(c) (4%) Is $2^{2n}$=O($2^n$)? 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($n^{log_2 3}$) 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 $\lfloor n/4 \rfloor$-th largest element for a given n-element set. Justify the time complexity of your algorithm.