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

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.