# 2001 F

*216,210*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%) 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.