CMSC 435 Algorithm Analysis & Design

CMSC 435 Algorithm Analysis & Design

Answers to Homework # 10

1. (Text, Chapter 6 # 5) let s[1..n] be the string of characters. The last word ends at character s[n] and must start with some character s[j]. Is this problem like one we have done previously? The first example that comes to mind is the matrix-chain multiplication problem. Is factoring this string of letters similar in some way to the problem of optimally factoring a string of matrices? Let P(1,n) = maximum quality in a string from 1 to n. Then P(1, n) = the greater of the max quality in the entire string or the max₁_£k<n(P(1,k) + P(k+1,n)). Let quality(char[] chs) be an auxiliary function that returns an int value that may be negative if the string does not match any known English word. Here is a sketch of the algorithm:

Create table[n][n]

for (int i = 1; i <= n; i++)

M[i][i] = quality(s[i]); //diagonal contains quality of each one char string (only a, I positive)

for (int l = 2; l <= n; l++) //for strings of length 2 .. n

for (i = 1; i < n-l+1; i++) { //starting at index i

j = i + l - 1; //ending at index j

M[i][j] = quality(s[i]…s[j]); //default is quality of the whole string from s[i] to s[j]

for (int k = 1; k < j; k++) { //find quality of all possible substrings

int temp = M[i][k] + M[k+1][j];

if (temp > M[i][j]) //when more quality factorization found, take it

M[i][j] = temp;

}

2. (Text, Chapter 6 # 6) The last line ends with the word w_n and has to start with some word w_j. Breaking off words w_j…w_n, we are left with the recursive sub-problem of optimizing the printing of the first j-1 words. Let S_i,j denote the slack of a line containing the words w_i, …,w_j. We define S_i,j = ¥ if these words exceed the line length L. Create a table S[n][n] where S[i][j] is the slack in the string from w_i through w_j. Cost of creating this table is O(n²). Then we have the recurrence OPT[n] = min₁_£j_£n(S_j,n² + OPT[j-1]). Construct an array OPT[0..n]

Create a table S for determining the slack for each substring grouping from w_i through w_j

Let int [][] S = new int[n+1][n+1]

for(int i = 1; i <= n; i++)

S[i][0] = L; // Lines beginning at word(i) are empty and slack = L

for (int i = 1; i <= n; i++)

for (int j = i; j <= n; j++) {

int temp = 0;

for (int k = i; k < j; k++) {

temp = S[i][k-1] – c[k] -1; //previous slack reduced by length of k^th word + 1

if (temp < 0) {

S[i][j] = ∞;

}

temp -= c[j];

if (temp >= 0)

S[i][j] = temp;

}

Compute all values S[i][j] as described above

Set OPT[0] = 0

for (int k = 1; k <= n; k++)

OPT[k] = min₁_£j_£k (S_j,k² + OPT[j-1])

return OPT[n]

3. (Text, Chapter 6 # 19) Let s, the received signal be n bits long. Consider x', a repetition of x, and y', a repetition of y to both consist of exactly n characters (thus with these elongated strings we don't have to consider wrap around because it has already been accounted for). This problem is somewhat similar to the LCS problem we discussed in class. Let x'[i] denote the i^th bit of x' and y'[j] the j^th bit of y'. Then s[1 : i+j] is an interleaving of x'[1 : i] and y'[1 : j] if s[i+j] = x'[i] and s[1 : i+j-1] is an interleaving of x'[1 : i-1] and y'[1 : j] or s[i+j] = y'[j] and s[1 : i+j-1] is an interleaving of x'[1 : i] and y'[1 : j - 1]. Construct an (n+1) x (n+1) array of Booleans, M, with entries M[i][j] = true if and only if M[i-1][j] = true and s[i+j] = x'[i], or M[i][j-1] = true and s[i+j] = y'[j].

Construct an algorithm with the following loop:

M[0][0] = true;

for (int k = 1; k <= n; k++)

for (int i = 1; i < k; i++) {

j = k - i;

if ( M[i-1][j] && s[i+j] = x'[i])

M[i][j] = true;

else if (M[i][j-1] && s[i+j] = y'[j])

M[i][j] = true;

else

M[i][j] = false;

}

return true if M[i][j] = = true for some (i + j) = n

4. (Text, Chapter 6, # 28)

a) Order the jobs by increasing order of their deadline. Let J be an optimal subset of the jobs that are scheduled to complete before their deadline. The minimum lateness of all of the jobs in J is 0 -- all jobs in J meet deadline. See pages 129 - 131 of the text to verify that the greedy choice of ordering all the jobs by increasing deadline minimizes the maximum lateness (sum of the differences between ending time and deadline for all of the jobs not meeting deadline). Hence ordering jobs in J by their deadline generates a feasible schedule for this set of jobs.

b) This is like the subset-sum problem (exact-fit knapsack). Order the jobs by increasing deadline: d₁ £ d₂ £ …£ d_n = D = "the size of the knapsack". Let OPT(m, d) be the maximum subset of the first m jobs that can be scheduled by time d. where 0 £ d £ D for m = 0.. n. Then we either include job m in the optimal set, or leave it out, and OPT(m, d) = max (OPT(m-1, d), OPT(m-1, d-t_m)+1). This gives the following algorithm:

public static Cell[][] selectJobs(int n, int D) {

Cell[][] table = new Cell[m+1][D+1];

for (int j = 0; j <= D; j++) {

table[0][j].size = 0;

table[0][j].belongs = false;

}

for (int m = 1; m <= n; m++)

for (int d = 0; d <= D; d++) {

table[m][d].size = table[m-1][d].size;

table[m][d].belongs = false;

if (d - t_m) >= 0 && d_m <= d && table[m-1][d - t_m].size + 1) > table[m][d].size) {

table[m][d].size = table[m-1][d-t_m].size + 1;

table[m][d].belongs = true;

}

return table;

}