# 1998 F

212,726pages on
this wiki

1. (12%) When an adjacency-matrix representation is used, most graph algorithms require O(|V|) time, where V denotes the vertex set. But there are some exceptions. A vertex of a graph is a sink if it has in-degree |V|-1 and out-degree 0.

(a) (5%) Show that determining whether a graph contains a sink can be done in O(|V|) time if the graph is represented by adjacency lists.
(b) (7%) Show that determining whether a graph contains a sink can be done in O(|V|) time even if the graph is represented by an adjacency matrix.

2. (15%) The following is Prim's minimum spanning tree algorithm.

MST-PRIM(G, w, r)
/* In the following, Q is a priority queue that stores a set of vertices. The priority of a vertex v in Q is denoted by key[v]. */
1. for each u∈V[G]
2. do key[u]←∞
3. key[r]←0
4. Q←V[G]
5. π[r]←NIL
6. while Q≠∅
7. do u←Extract-Min(Q)
8. for each v∈Adj[u]
9. do if v∈Q and w(u,v) < key[v]
10. then π[v]←u
11. key[v]←w(u,v)

Suppoer that G is represented by adjacency lists and the priority queue Q is implemented as a binary heap.

(a) (5%) What's the running time of Steps 1~4 (in terms of |V| and |E|)? Justify your answer.
(b) (5%) Step 7 will be executed |V| times. What is the overall time complexity of this step? Justify your answer.
(c) (5%) Steps 8~11 will be executed |V| times. What is the overall time complexity ofthese steps? Justify your answer.

3. (5%) Show that the problem of finding the maximum flow of a network with multiple sources and sinks is no hard than the problem of finding the maximum flow of a network with just one source and one sink.

4. (8%) Consider a weighted graph G. G has n vertices, labeled from 1 to n. Let W be an array such that if there is an edge between vertex i and ver j, $w_{i.j}$ stores the length of the edge; otherwise, $w_{i,j}$ stores ∞. Define $d_{i,j}^{m}$ as the minimum length of any path from vertex i to vertex j that contains at most m edges.

(a) (3%) What is the value $w_{i,j}^{0}$?
(b) (5%) For m>0, write a recurrence of $d_{i,j}^{m}$.

5. (5%) For each of the following statements, determine wheather it is correct or not.

(a) The lower bound of NP-hard problem is exponential if and only if P≠NP is proved.
(b) The lower bound of NP-hard problem is exponential once if P≠NP is proved.
(c) Suppose that it is proved that the lower bound of the satisfiability problem is polynomial, we can conclude that P=NP.
(d) It is proved that the problem of determinining whether a given number is prime or not can be solved in polynomial time by a deterministic algorith.
(e) It is proved that the problem of determining whether a given number is prime or not is NP-complete.

6. (15%) Illustrate a problem example and a greedy algorithm. Prove that your algorithm solve the problem correctly.

7. (10%) Find the solution of the following recurrences.

(a) T(n)=2T(n/2)+O($n^{0.3}$)
(b) T(n)=143640T(n/70)+Θ($n^2$)

8. (10%) Prove that we can build a heap from an unordered array in linear time.

9. (10%) Given an O(nlgk)-time algorithm to merge k sorted lists into one, where n is the total number of elements in all the input lists.

10. (10%) (Viterbi algorithm for speech recognition) Given a directed graph G=(V,E), each edge (u,v)∈E is labeled with a sound σ(u,v) from a finite set Σ of sounds. The labeled graph is a formal model of a person speaking a restricted language. Each path in the graph starting from a distinguished vertex $v_0$∈V corresponding to a possible sequence of sounds produced by the model. The label of a directed path is defined to be the concatenated of the labels of the edges on that path. Describe an efficient algorithm that, given an edge-labeled graph G with distinguished vertex $v_0$ and a sequence s=($\sigma_1, \sigma_2, ..., \sigma_k$) of characters from Σ, returns a path in G that begins at $v_0$ and s as its label, if any such path exists. Otherwise, the algorithm should return NO-SUCH-PATH. Analyze the running time of your algorithm.