## FANDOM

235,761 Pages

1. (10%) Show that multiplying tow n*n matrices requires O($n^2logn$) time if there is a way to multiply two 3*3 matrices using 9 multiplications (not assuming commutativity of multiplication).

2. (10%) Let P be a set of n points on the 2-dimensional Eucliean plane. Let T be a minimum spanning tree of P and let U be an optimal traveling-salesman tour of P.

(a) (3%) Prove that |T|≤|U|, wher |T| and |U| are the lengths of T and U. respectively.
(b) (7%) Prove that |U|≤2|T|.

3. (10%) Let A be a set of n positive numbers. The partition problem is to determine whether we can partition A into two subsets $A_1$ and $A_2$ such that [/itex]\sum_{i \in A_1} i= \sum_{i \in A_2} i[/itex]. It is well-known that the partition problem is NP-complete. Let k > 2 be an integer. Define the k-partition problem as to determine whether we can partition A into k subsets $A_j$, j=1, 2, ..., k such that all $\sum_{i \in A_j} i$ are equal. Prove that k-partition problem is NP-complete.

4. (10%) Describe an algorithm that, given n integers in the range of 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.

5. (10%) Give asymptotic upper bounds for T(n) in the following recurrences. Assume that T(n) is constant for n≤2. Make your bounds as tight as possible, and justify your answers.

(a) T(n)=T($\sqrt{n}$)+1
(b) T(n)=$\sqrt{n}$T($\sqrt{n}$)+n

6. (15%) Given two string x[1..m] and y[1..n] and a given set of operation costs, the edit distance between x and y is the least expensive transformation sequence that converts x to y. Suppose the given set of operations and associated costs are listed as follows:

 Operation Description Associated Costs Delete Delete a character $C_d$ Replace Replace a character $C_r$ Copy Copy a character $C_c$ Insert Insert a character $C_i$ Twiddle Interchange two adjacent characters $C_t$ Kill Kill to end of line $C_d$

For example, the following table shows how to use the above operation to change the source string x="algorithm" into a target string y="altruistic":

 Operation Target string Source string Copy a a lgorithm Copy l al gorithm Replace g by t alt orithm Delete o alt rithm Copy r altr ithm Insert u altru ithm Insert i altrui ithm Insert s altruis ithm Twiddle it into ti altruisti hm Insert c altruistic hm Kill hm altruistic

The cost of the above transformation sequence is $3C_c+C_r+C_d+4C_i+C_T+C_k$.

(a) (10%) Describe a dynamic-programming algorithm to find the edit distance from x[1..m] to y[1..n]. (Please clearly define your notation.)
(b) (5%) Analyze the running time and space requirements of your algorithm (in terms of big-O notation).

7. (10%) Let (u,v) be a minimum-weight edge in a graph G=(V,E). Show that (u,v) belongs to some minimum spanning tree of G.

8. (15%)

(a) (3%) Define the maximum-flow problem in detail.
(b) (7%) Describe a basic Ford-Fulkerson algorithm for the maximum-flow problem and discuss its time complexity.
(c) (5%) Show the execution of the Edmonds-Karp algorithm on the following flow network.

9. (10%)

(a) (5%) Describe the Dijkstra's algorithm for solving the single-source shortest-paths problem on a weighted, directed graph G=(V,E) with all non-negative edge weights.
(b) (5%) If a Fibonacci heap is used, what is the running time of Dijkstra's algorithm (In big-O notation)? Explanation is necessary.