CSE 521 Assignment #2
Winter 2010

Due: Thursday, February 4, 2010 in class.

Reading Assignment: Kleinberg and Tardos Chapter 6. Start reading Chapter 7.

Instructions: You are allowed to collaborate with fellow students taking the class in solving problem sets. However, you must write up your problem sets individually. If you do collaborate in any way, you must acknowledge for each problem the people you worked with on that problem.

The problems have been chosen for their pedagogical value and hence might be similar or identical to those given out in past offerings of this course at UW, or similar courses at other schools. Using any pre-existing solutions from these sources, from the Web or other algorithms textbooks constitues a violation of the academic integrity expected of you and is strictly prohibited.

Most of the problems require only one or two key ideas for their solution. In writing up your solutions make sure that you clearly write out the main ideas of your solution first so that if you make a mistake in the details you can still get good partial credit for the problem. After you sketch out your solution try to clean up your presentation to make sure that you are only making necessary correct claims since additional incorrect claims will hurt your score.

Please typeset solutions for legibility and hand in hard copies. (The goal for this is not to be time-consuming so don't waste time using drawing programs; hand-drawn diagrams are OK.)

Whether or not the problem asks for it explicitly, you are required to prove that your algorithms do what you claim.

A final piece of advice: Begin work on the problem set early and don't wait till the deadline is only a few days away.

Problems: Whether or not the questions ask for it explicitly, your algorithms must be companied by a runtime analysis.

1. Use the same ideas as used to solve the problem for closest pair in the plane to create an O(n log² n) algorithm for finding closest pairs in 3 dimensions. (This is not optimal; an O(n log n) algorithm exists that uses ideas of the above algorithm plus more flexibility in choosing how to split the points into subproblems so that the difficult strip in the middle has fewer points.)

2. We saw how Karatsuba's algorithm could be viewed as based on a method for multiplying two degree 1 polynomials using 3 multiplications of coefficients based on evaluation and interpolation at 3 points.

   1. Show how to multiply two degree 2 polynomials using only 5 multiplications of coefficients plus linear combinations based on multiplication by fixed constants (6 is easy but results in a worse algorithm than Karatsuba's).

   2. Use part (a) to improve the running time of Karatsuba's algorithm for multiplying degree n polynomials and give the running time of your improved algorithm.

   3. Generalize Karatsuba's algorithm and part (a) to show how to multiply two degree k polynomials using only 2k+1 multiplications of coefficients.

   4. Use part (c) in the analog of part (b) and give the running times of the resulting improved algorithms.

3. Given an n-vertex undirected tree T=(V,E) with weight function w on its edges, we wish to find a maximum matching in T, namely a maximum weight subset of edges that forms a matching (not necessarily perfect). Since trees are bipartite, one can use maxflow techniques to compute a maximum weight matching in T in polynomial time but this is overkill. Derive an O(n) time algorithm for the problem.

4. Kleinberg and Tardos, Chapter 6, Problem 14, pages 324-325.

5. Kleinberg and Tardos, Chapter 6, Problem 25, pages 332-333.

6. Let A be a finite alphabet. For two strings s and t over alphabet A we say that s is a subsequence of t (and t is a supersequence of s) if all symbols in s appear in order but not necessarily consectively in t. For strings x and y over alphabet A, define LCS(x,y) to be the longest common subsequence of x and y. (That is, the longest string s that is a subsequence of both x and y.) Similarly define SCS(x,y) to be the shortest common supersequence of x and y.

   1. Give a polynomial-time algorithm to compute ID(x,y), the minimum total number of insert and delete operations needed to convert x to y, as well as the sequence of those operations achievng the minimum.

   2. Give a polynomial-time algorithm to compute both LCS(x,y) and SCS(x,y) using the algorithm in part (a).