1. (10%) Show that multiplying tow n*n matrices requires O() 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 and such that </math>\sum_{i \in A_1} i= \sum_{i \in A_2} i</math>. 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 , j=1, 2, ..., k such that all 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()+1
- (b) T(n)=T()+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 | |

Replace | Replace a character | |

Copy | Copy a character | |

Insert | Insert a character | |

Twiddle | Interchange two adjacent characters | |

Kill | Kill to end of line |

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 .

- (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.