1998 S

212,773pages on
this wiki
Add New Page
Add New Page Discuss this page0

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.

Also on Fandom

Random wikia