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, stores the length of the edge; otherwise, stores ∞. Define 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 ?
- (b) (5%) For m>0, write a recurrence of .
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()
- (b) T(n)=143640T(n/70)+Θ()
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 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 and a sequence s=() of characters from Σ, returns a path in G that begins at 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.