2001 F

219,207pages on
this wiki
Add New Page
Discuss this page0 Share

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.

Also on Fandom

Random wikia