# 1999 S

*215,986*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. (10%) The linear time string matching algorithm proposed by Knuth, Morris, and Pratt finds the occurrences of a pattern P[1..m] in a text T[1..n] by utilizing the prefix function π os P.

- (a) (5%) Write the definition of π.
- (b) (5%) Let m=10 and P=ababcababa. Give the values of π[i]. for i=1, 2, ..., 10.

2. (10%) What is the largest k such that if you can multiply 3 by 3 matrices using k multiplications (not assuming commutativity of multiplication), then you can multiply n by n matrices in time o()? What would the running time of this algorithm be? You should justify your answers.

3. (15%) Use Ford-Fulkerson's method for the maximum flow problem to find a maximum matching for the following bipartite graph. While applying Ford-Fulkerson's method, you should describe the steps in detail instead of calling it as a procedure. What is the time complexity of your algorith?

4. (10%) Let G=(V,E) be a weighted directed graph. Let V={1, 2, ..., n} and be the non-negative distance between vertex i and vertex . Let , 1≤a,b≤n and q≤n, be the distance of a shortest path from vertex a to vertex b with all intermediate vertices in the set ={n-q+1, n-q+2, ..., n}. (In case q≤0, is an empty set.) Give a recurrence for .

5. (10%) Let A[1..n] be an array storing all the existing telephone numbers in Taipei area. Give an O(n) time algorithm to sort the elements of A.

6. (10%) Consider the recurrence: f(n)=f(g(n))+c, where c is a constant. You have seen two algorithms whose costs fit this recurrence but which have two growth rates. In linear search g(n)=n-1 and in binary search g(n)=n/2. The respective growth rates of f are O(n) and O(lgn). If we want to design a search algorithm that has O(lglglgn) time, what g should we look for?

7. (10%)

- (a) (5%) Describe an approximation algorithm with ratio bound 2 for the vertex cover problem.
- (b) (5%) Prove that your algorithm has a ratio bound 2.

8. (15%) We all know the SATISFIABILITY problem is NP-compete. The k-SATISFIABILITY problem is similar to the SATISFIABILITY problem with more restriction: Every clause must contain exactly k literals. Prove that 3-SATISFIABILITY problem is NP-complete.

9. (10%) Huffman gave a greedy algorithm that constructs an optimal prefix code called Huffman code. Prove the correctness of the greedy algorithm.