# 1998 F

*215,972*pages 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. (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.