CS294-3: Algorithms in the real world Assignment 5 (VLSI and Pattern Matching) Due: Friday Nov 21, 1997

Please feel free to send me email if there are any ambiguous questions.

Problem 1: Consider the following graph.

A. Find a minimum cost Rectilinear Steiner Tree (RST) for the following set of points (the shaded points are the demand points).

B. Is this an S-RST? If not show the minimum cost S-RST.

Problem 2: For the following routing problem the three nets A, B and C need to be connected. The numbers on the edges represent their lengths, and assume that the capacity of every edge is 2.

A. Specify an integer (0-1) program for which the solution gives the minimum total wire length.

B. Solve the program (you do not need to show your work).

Problem 3: Describe an O(nm) time O(n + m) space algorithm for finding a minimum cost alignment assuming an affine gap cost model. Pseudocode with comments would be the best way to describe it.

Problem 4: (Extra Credit.) Describe an O(nm log(m + n)) time algorithms for finding a minimum cost alignment assuming the gap cost function x(k) (where k is the length of the gap) is concave downward (i.e. the second derivative is always negative).