February 5, 2010
Douglas Holmes
COMP510
Spring 2011
Assignment 1
a) Matrix Chain Multiplication
15.2.1 - Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is: (5, 10, 3, 12, 5, 50, 6).
Our equation for the Matrix Chain Product is given in the course book on page 374, and is as follows:
m[i,j] = {0 if i = j}, {MIN (m[i,k] + m[k + 1, j] + pi-1pkpj) if i < j}
If we apply this equation to the sequence of dimensions provided by the problem, we get the following m-table:
| m | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 150 | 330 | 405 | 1655 | 2010 |
| 2 | x | 0 | 360 | 330 | 2430 | 1950 |
| 3 | x | x | 0 | 180 | 930 | 1770 |
| 4 | x | x | x | 0 | 3000 | 1860 |
| 5 | x | x | x | x | 0 | 1500 |
| 6 | x | x | x | x | x | 0 |
Based on the m-table, we can calculate an s-table where each individual record represents the optimal splitting point.
| s | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 1 | 2 | 2 | 4 | 2 |
| 2 | x | 0 | 2 | 2 | 2 | 2 |
| 3 | x | x | 0 | 3 | 4 | 4 |
| 4 | x | x | x | 0 | 4 | 4 |
| 5 | x | x | x | x | 0 | 5 |
| 6 | x | x | x | x | x | 0 |
Applying the s-table to the PRINT-OPTIMAL-PARENS algorithm, demonstrated in the course book on page 377, gives us the optimal parenthesization requested by the problem, which is ((A5x10 A10x3)(A3x12 A12x5)(A5x50 A50x6))
15.2.2 - Give a recursive algorithm MATRIX-CHAIN-MULTIPLY (A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices {A1, A2, ..., An}, the s table computed by MATRIX-CHAIN-ORDER, and the indices i and j. (The initial call would be MATRIX-CHAIN-MULTIPLY (A, s, 1, n).)
Assuming that all variables are accounted for, the algorithm would look something like this:
MATRIX-CHAIN-MULTIPLY (A, s, i, j)
if(i = j) return A[i]
else if(j - i = 1) return MATRIX-MULTIPLY(A[i], A[j])
else return MATRIX-MULTIPLY(MATRIX-CHAIN-MULTIPLY(A, s, i, s[i,j]), MATRIX-CHAIN-MULTIPLY(A, s, s[i,j]+1, j))
So if n were 1, we'd get A[1]; if n were 2, we'd get MAXTRIX-MULTIPLY(A[1], A[2]); if n were 3, we'd get MATRIX-MULTIPLY(MATRIX-CHAIN-MULTIPLY(A, s, 1, s[1,3]), MATRIX-CHAIN-MULTIPLY(A, s, s[1,3]+1, 3)), etc.
b) Bitonic Traveling Salesman Problem
15.1 - Describe an O(n2)-time algorithm for determining the optimal bitonic tour. You may assume that no two points have the same x-coordinate. Hint: scan left to right, maintaining optimal possibilities for the two parts of the tour.
To start, assume we have n points. We then compute the distance between the points i and j, for every i,j such that 1 ≤ i < j ≤ n. This brute-force solution provides the shortest bitonic path between any two points 1 through n.
There are three cases we need to evaluate, much like we did for the MATRIX-CHAIN-MULTIPLY algorithm:
CASE 1: Only 2 points exist in the plane. Ergo, the shortest distance is the path between then.
CASE 2: More than 2 points exist in the plane, the start and end point (i and j) are connected, and there is a point that is also connected to both i and j. Ergo, we must calculate the distance between points i,j and another neighbor, k, such that for j>i+1, i
CASE 3: More than 2 points exist in the plane, the start and end point (i and j) are not connected. For this case, we have to use the technique from above, and apply it recursively in order to find the optimal path (at worst, n times each).
All cases considered, this would take O(n2) time in the worst possible case (both points not being connected, algorithm having to run through i and j n times).
c) Printing Neatly
15.2 - Give a dynamic programming algorithm to print a paragraph of n words neatly on a printer. Analyze the run time and space requirements for your algorithm.
To start, assume that no word is longer than will fit into a line, i.e. line M for all i.
We will also need to keep in mind the extra spaces at the end of a line, along with the cost of including a line containing words i through j in the sum. This gives us an equation lc[i,j] = {∞ if the words don't fit on the line, 0 for the very last line, and the summation of extra spaces otherwise.
In order to minimize lines, we want to arrange the words such that the extra spaces at the end of each line are minimized. This optimal arrangement will give us the shortest paragraph length.
Let c[j] be the cost of an optimal arrangement of words 1 through j. Since a line with words i through j contains j – i + 1 words, we know j – i + 1 ≤ M/2. Assume the line in question is the last line of the paragraph. This means that the preceeding lines contain the words 1 through (i-1).
From this, we can form the equation: c[j] = {0 if j = 0}, {MIN (c[i-1] + lc[i,j]) if j < 0}.
Using this equation, we can compute a table of values containing the ordered optimal points in the paragraph. This is detailed in the following algorithm:
PRINT-NEATLY(l, n, M)
for i = 1 to n:
e[i, i] = M − li
for j = i + 1 to n:
e[i, j] = e[i, j − 1] − lj – 1
for i = 1 to n:
for j = i to n:
if e[i, j] < 0:
lc[i, j] = ∞
else if j = n and e[i, j] ≥ 0:
lc[i, j] = 0
else:
lc[i, j] = (e[i,j])3
c[0] = 0
for j = 1 to n:
c[ j ] = ∞
for i = 1 to j:
if c[i − 1] + lc[i, j] < c[j]:
c[j] = c[i − 1] + lc[i, j]
p[j] = i
return c and p
References:
- Course Textbook: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition.
- http://mitpress.mit.edu/algorithms/solutions/chap15-solutions.pdf