CECS 419/619 COMPUTER ALGORITHMS Fall 2016
Homework Set 5
Student Name: Khaled Gamal Abdel Maksoud
Student ID: 1280703
Problem 1
Determine an LCS of {1; 0; 0; 1; 0; 1; 0; 1} and {0; 1; 0; 1; 1; 0; 1; 1; 0}. You need to illustrate your
intermediate results by providing the c matrix and showing how you reconstruct the LCS by tracing backwards.
Solution
The c matrix is shown in Table 1.
1 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1
1 0 1 1 1 2 2 2 2 2
0 0 1 2 2 2 3 3 3 3
1 0 1 2 2 3 3 4 4 4
j
1 0 1 2 2 3 3 4 4 5
0 0 1 2 3 3 4 4 5 5
1 0 1 2 3 4 4 5 5 6
1 0 1 2 3 4 4 5 5 6
0 0 1 2 3 4 5 5 6 6
Table 1 - The c Matrix.
As shown in Table 1, the length of the LCS is 6 and we can trace this 6 backwards, as indicated by the arrows,
in order to find an LCS. Accordingly, an LCS is {1; 0; 0; 1; 1; 0}.
Page 1 of 13
Problem 2
Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence (16.2, page
416). Have your algorithm compute the sizes c[i,j] as defined in (16.2) and also produce the maximum-size
subset of mutually compatible activities. Assume that the inputs have been sorted as in equation (16.1).
Compare the running time of your solution to the running time of GREEDY-ACTIVITY-SELECTOR.
Solution
The recurrence equation 16.2 is written as follows:
Sij is the set of all activities between activity ai and activity aj and we will search for the full solution when i = 0
and j = n+1 (where n is the number of activities).
If activity ak ∊ Sij, then we have i < k < j, which means that j - i ≥ 2. We must also have that fi ≤ sk and fk ≤ sj
where:
fi : the finish time of activity ai
fk : the finish time of activity ak
sk : the start time of activity ak
sj : the start time of activity aj
If we start k at j - 1 and decrement k, we can stop until k reaches i or we find those sk and fk.
We will use tables c[0…n + 1,0…n + 1] as in recurrence (16.2) where c[i,j] = |Aij|. We will use another table
ACT[0…n+1,0…n+1] where ACT[i,j] contains the activity k that we choose to put into Aij. We will fill these
tables based on the different values of j - i, which we denote by L in the proposed pseudo code of the algorithm.
The start and finish times of the n activities are given as arrays s and f and the proposed dynamic programming
algorithm is written as follows:
Page 2 of 13
DYNAMIC_PROGRAMMING_ACTIVITY_SELECTOR(s , f , n)
{
// Initialize table c[0…n + 1,0…n + 1]
For i = 0 to n
{
c[i,i] = 0;
c[i,i+1] = 0;
}
c[n+1,n+1] = 0;
// loop for different values of j – i as denoted by L
For L = 2 to n+1
{
For i = 0 to n - L + 1
{
j=i+L // since L = j - i
ACT[i,j] = -1; // initialize ACT[i,j]
If f[i] < s[j] // we can find an activity k in between
{
For k = i + 1 to j – 1
{
If s[k] >= f[i] and f[k] <= s[j] // activity k is compatible
{
temp = c[i,k] + c[k,j] + 1; // apply recurrence 16.2
If temp > c[i,j]
{
c[i,j] = temp;
ACT[i,j] = k; // insert activity k in activity table
}
}
}
}
}
}
// Print the solution to the problem
Print c[0,n+1];
Print ACT table;
}
At the end of the algorithm written above, c[0,n+1] will contain the size of the maximum subset of mutually
compatible activities and the ACT table will contain the elements of that maximum subset.
Referring to the algorithm written above, we have 3 nested “For Loops” in order to complete the required
computations for the optimal solution c[0 , n+1] and each loop takes about n passes. Hence, the running time of
this algorithm is O(n3) while the running time of the GREEDY-ACTIVITY-SELECTOR is O(n).
Page 3 of 13
Problem 3
Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(n W) time, where n is the
number of items and W is the maximum weight of items that the thief can put in his knapsack.
Solution
Define c[i,w] to be the value of the solution for items 1, 2, . . . , i and maximum weight w such that:
0 if i = 0 or w = 0
c[i,w] = c[i-1,w] if i>0 and wi ≥ w
max {vi + c[i-1,w-wi] , c[i-1,w]} if i>0 and w ≥ wi
This says that the value of the solution to i items either includes the ith item, in which case it is vi plus a
subproblem solution for (i-1) items and the weight excluding wi, or does not include the ith item, in which case it
is a subproblem's solution for (i-1) items and the same weight. We will have 2 arrays v and w holding the values
and weights of the n items respectively. The proposed dynamic programming algorithm is written as follows:
DYNAMIC_PROGRAMMING_KNAPSACK (v, w, n ,W)
{
// Initialize table c[0…n,0…W]
For i = 1 to n
{
For w = 1 to W
c[i,w] = 0;
}
// loop through the n items
For i = 1 to n
{
For w = 1 to W
{
If wi <= w // weight of the ith item is less than or equal to the remaining weight
{
If (vi + c[i-1,w-wi]) > c[i-1,w]
c[i,w] = vi + c[i-1,w-wi]; // include the ith item in the solution
else
c[i,w] = c[i-1,w]; // exclude the ith item from the solution
}
else
{
c[i,w] = c[i-1,w]; // exclude the ith item from the solution
}
}
}
}
Page 4 of 13
Referring to the algorithm written above, we have 2 nested “For Loops” in order to complete the required
computations for obtaining the optimal solution c[n,W]. The first loop takes n passes and the second one takes
W passes. Hence, the running time of this algorithm is O(n W).
Problem 4
Given a sequence of n real numbers A(1) ... A(n), (mixture of positive and negative numbers) give a dynamic-
programming solution that determines a contiguous subsequence A(i) ... A(j) for which the sum of elements in
the subsequence is maximized.
Solution
The optimal solution to this problem can be made up of optimal solutions to subproblems (optimal here means a
contiguous subsequence with the maximum sum of elements). If we find the optimal contiguous subsequence
ending at position j, for any j in {1, 2, …, n}, then we can always build our next solution out of previous ones.
For instance, we can solve for the sum of the optimal subsequence ending at position 1 and denoted by S(1) as
follows:
S(1) = A(1) (where A(1) is the 1st element of the input sequence)
Similarly, the sum of the optimal subsequence ending at position 2 and denoted by S(2) can be obtained as
follows:
S(2) = Max[ A(1)+A(2) , A(2) ], or
S(2) = Max[ S(1) + A(2) , A(2) ]
With each value of S, we need to keep the starting element of the sum. Then, we can scan all values of S in
order to determine the final optimal subsequence in terms of the maximum sum of elements along with the
starting and ending indexes.
Accordingly, we can construct the following recurrence to obtain the optimal subsequence ending at position j
as follows:
0 if j = 0
S(j) = max {S(j-1) + A(j) , A(j)} if j > 0
The proposed dynamic programming algorithm is written as follows:
Page 5 of 13
DYNAMIC_PROGRAMMING_MAX_SUM_CONTIGUOUS_SUBSEQUENCE (A , n)
{
// A is the input sequence
// n is the number of elements in the input sequence
// We will use table S to store the summations of subsequences
// Initialize variables used to compute the solution
S(0) = 0;
Starting_Index = 0;
Ending_Index = 0;
Max_Sum = 0;
// Fill table S based on the recurrence equation
For j = 1 to n
{
If ( S(j-1) + A(j) ) > A(j)
{
S( j) = S(j-1) + A(j) ;
Store the starting index for sum S(j) ;
}
else
{
S( j) = A(j) ;
Store the starting index for sum S(j) ;
}
}
// Scan the S table to find the contiguous subsequence with the maximum sum of elements
For j = 1 to n
{
If S( j) > Max_Sum
{
Max_Sum = S( j);
Starting_Index = Retrieve Starting Index of S(j);
Ending_Index = j;
}
}
Print Max_Sum, Starting_Index, and Ending_Index ; // Print the solution to the problem
}
Referring to the algorithm written above, we have 2 separate “For Loops” in order to complete the required
computations for obtaining the optimal solution and each loop takes n passes. Hence, the running time of this
algorithm is O(2n) which is equivalent to O(n).
Page 6 of 13
Problem 5
Given a sequence of n real numbers A(1) ... A(n), give a dynamic-programming solution that determines a
subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a
strictly increasing sequence.
Solution
The optimal solution to this problem can be made up of optimal solutions to subproblems (optimal here means a
strictly increasing subsequence with the maximum length). Let L(j) denote the length of the longest strictly
increasing subsequence possible which ends at position j. For each value L(j), we need to keep the starting
element of the subsequence whose length is represented by L(j).
Once we have computed L(j) for j = 1, 2, …, n then to find the length of the subsequence of maximum length in
which the values are strictly increasing, we simply take the maximum of L(j) over all j, 1 ≤ j ≤ n. We can
construct the following recursive relationship:
0 if j = 0
L(j) = 1 + max{L(i) | A(i) < A(j) and i < j} if j > 0
The proposed dynamic programming algorithm is written as follows:
DYNAMIC_PROGRAMMING_MAX_LENGTH_INCREASING_SUBSEQUENCE (A , n)
{
// A is the input sequence
// n is the number of elements in the input sequence
// We will use table L to store the lengths of subsequences
L(0) = 0;
Starting_Index = 0; Ending_Index = 0; // Initialize variables used to compute the solution
A(0) = - ∞; // dummy element that is smaller than all elements of A
// Fill table L based on the recurrence equation
For j = 1 to n
{
temp_max_length = 0;
For i = 0 to j-1
{
If A(j) > A(i) and L(i) >= temp_max_length
{
temp_max_length = L(i) ;
L( j) = 1 + temp_max_length ;
Store the starting index for L(j) ;
}
}
}
Page 7 of 13
// Scan the L table to find the longest strictly increasing subsequence
Max_Length = 0;
For j = 1 to n
{
If L( j) >= Max_Length
{
Max_Length = L( j);
Starting_Index = Retrieve Starting Index of L(j);
Ending_Index = j;
}
}
Print Max_Length, Starting_Index, and Ending_Index ; // Print the solution to the problem
}
Referring to the algorithm written above, filling table L will take (1+2+3+…+n) = O(n2) running time. Scanning
table L to get the final optimal solution will take O(n) running time. Hence, the total running time of this
algorithm is O(n2) + O(n) = O(n2).
Page 8 of 13
Extra Credit Problem
A. Theoretical part
i. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 10, 3, 12, 5,
50, 6>. (A1 is 5x10, A2 is 10x3, …, A6 is 50x6). You need to illustrate your intermediate results by providing
the m and s matrices (refer to lecture slides).
ii. In how many different ways can you parenthesize the product of the 6 matrices?
B. Experimental part
i. Write a function that computes the product of 6 matrices with a given parenthesized order
ii. Call the function with each unique parenthesized order (determined above)
iii. Record the time for each order
iv. Plot the time and compare the option that resulted in the minimum time to the one identified in the
theoretical part.
Solution
A. Theoretical part
i. Find an optimal parenthesization of the matrix-chain product.
The dimensions of the given matrices are:
A1 = 5 x 10 (P0 x P1)
A2 = 10 x 3 (P1 x P2)
A3 = 3 x 12 (P2 x P3)
A4 = 12 x 5 (P3 x P4)
A5 = 5 x 50 (P4 x P5)
A6 = 50 x 6 (P5 x P6)
The m values are computed as follows:
m[1,1] = m[2,2] = m[3,3] = m[4,4] = m[5,5] = m[6,6] = 0
m[1,2] = m[1,1] + m[2,2] + P0P1 P2 = 150 [ k = 1 ]
m[2,3] = m[2,2] + m[3,3] + P1P2 P3 = 360 [ k = 2 ]
m[3,4] = m[3,3] + m[4,4] + P2P3 P4 = 180 [ k = 3 ]
m[4,5] = m[4,4] + m[5,5] + P3P4 P5 = 3000 [ k = 4 ]
m[5,6] = m[5,5] + m[6,6] + P4P5 P6 = 1500 [ k = 5 ]
m[1,3] = min{ (m[1,1] + m[2,3] + P0P1 P3) , (m[1,2] + m[3,3] + P0P2 P3) }
= min{ (0 + 360 + 600) , (150 + 0 + 180) }
= min{ 960 , 330 } = 330 [ k = 2 ]
Page 9 of 13
m[2,4] = min{ (m[2,2] + m[3,4] + P1P2 P4) , (m[2,3] + m[4,4] + P1P3 P4) }
= min{ (0 + 180 + 150) , (360 + 0 + 600) }
= min{ 330 , 960 } = 330 [ k = 2 ]
m[3,5] = min{ (m[3,3] + m[4,5] + P2P3 P5) , (m[3,4] + m[5,5] + P2P4 P5) }
= min{ (0 + 3000 + 1800) , (180 + 0 + 750) }
= min{ 4800 , 930 } = 930 [ k = 4 ]
m[4,6] = min{ (m[4,4] + m[5,6] + P3P4 P6) , (m[4,5] + m[6,6] + P3P5 P6) }
= min{ (0 + 1500 + 360) , (3000 + 0 + 3600) }
= min{ 1860 , 6600 } = 1860 [ k = 4 ]
m[1,4] = min{ (m[1,1] + m[2,4] + P0P1 P4) , (m[1,2] + m[3,4] + P0P2 P4) , (m[1,3] + m[4,4] + P0P3 P4) }
= min{ (0 + 330 + 250) , (150 + 180 + 75) , (330 + 0 + 300) }
= min{ 580 , 405 , 630 } = 405 [ k = 2 ]
m[2,5] = min{ (m[2,2] + m[3,5] + P1P2 P5) , (m[2,3] + m[4,5] + P1P3 P5) , (m[2,4] + m[5,5] + P1P4 P5) }
= min{ (0 + 930 + 1500) , (360 + 3000 + 6000) , (330 + 0 + 2500) }
= min{ 2430 , 9360 , 2830 } = 2430 [ k = 2 ]
m[3,6] = min{ (m[3,3] + m[4,6] + P2P3 P6) , (m[3,4] + m[5,6] + P2P4 P6) , (m[3,5] + m[6,6] + P2P5 P6) }
= min{ (0 + 1860 + 216) , (180 + 1500 + 90) , (930 + 0 + 900) }
= min{ 2076 , 1770 , 1830 } = 1770 [ k = 4 ]
m[1,5] = min{ (m[1,1] + m[2,5] + P0P1 P5) , (m[1,2] + m[3,5] + P0P2 P5) , (m[1,3] + m[4,5] + P0P3 P5) ,
(m[1,4] + m[5,5] + P0P4 P5) }
= min{ (0 + 2430 + 2500) , (150 + 930 + 750) , (330 + 3000 + 3000) , (405 + 0 + 1250) }
= min{ 4930 , 1830 , 6330 , 1655 } = 1655 [ k = 4 ]
m[2,6] = min{ (m[2,2] + m[3,6] + P1P2 P6) , (m[2,3] + m[4,6] + P1P3 P6) , (m[2,4] + m[5,6] + P1P4 P6) ,
(m[2,5] + m[6,6] + P1P5 P6) }
= min{ (0 + 1770 + 180) , (360 + 1860 + 720) , (330 + 1500 + 300) , (2430 + 0 + 3000) }
= min{ 1950 , 2940 , 2130 , 5430 } = 1950 [ k = 2 ]
m[1,6] = min{ (m[1,1] + m[2,6] + P0P1 P6) , (m[1,2] + m[3,6] + P0P2 P6) , (m[1,3] + m[4,6] + P0P3 P6) ,
(m[1,4] + m[5,6] + P0P4 P6) , (m[1,5] + m[6,6] + P0P5 P6) }
= min{ (0 + 1950 + 300) , (150 + 1770 + 90) , (330 + 1860 + 360) , (405 + 1500 + 150) ,
(1655 + 0 + 1500) }
= min{ 2250 , 2010 , 2550 , 2055 , 3155 } = 2010 [ k = 2 ]
Page 10 of 13
The m and s matrices are shown in Table 2 and Table 3 respectively.
1 2 3 4 5 6
6 2010 1950 1770 1860 1500 0
5 1655 2430 930 3000 0
4 405 330 180 0
j
3 330 360 0
2 150 0
1 0
i
Table 2 - The m Matrix
1 2 3 4 5 6
6 2 2 4 4 5 0
5 4 2 4 4 0
4 2 2 3 0
j
3 2 2 0
2 1 0
1 0
i
Table 3 - The s Matrix
Referring to the s matrix in Table 2, we have:
s[1,6] = 2 which is translated to (A1 A2) (A3 A4 A5 A6).
s[3,6] = 4 which is translated to (A3 A4) (A5 A6).
Accordingly, the optimal parenthesization will be ( (A1 A2) ( (A3 A4) (A5 A6) ) ).
Page 11 of 13
ii. How many different ways can you parenthesize the product of the 6 matrices?
In order to answer the previous question, we will follow an incremental approach as detailed in the following
text. Let P(n) denote the number of different ways to parenthesize the product of n matrices. Our objective is to
compute P(6).
It is clear that the product of 2 matrices M1 and M2 can be parenthesized in only 1 way.
Now, suppose that we have 3 matrices named M1, M2, and M3. Then, the product of M1*M2*M3 can be
parenthesized in 2 different ways: (M1*M2)*M3 and M1*(M2*M3).
Accordingly, P(3) = 2 (A)
Now, suppose that we have 4 matrices named M1, M2, M3, and M4. Then, the product of M1*M2*M3*M4 can
be split at 3 different positions: M1*(M2*M3*M4), (M1*M2)*(M3*M4), and (M1*M2*M3)*M4.
The product (M1*M2)*(M3*M4) can be parenthesized in only 1 way.
Using equation (A) written above, both of the 2 products M1*(M2*M3*M4) and (M1*M2*M3)*M4 can be
parenthesized in 2 different ways.
Accordingly, P(4) = P(3) + 1 + P(3) = 2 + 1+ 2 = 5 (B)
Now, suppose that we have 5 matrices named M1, M2, M3, M4, and M5. Then, the product of
M1*M2*M3*M4*M5 can be split at 4 different positions: M1*(M2*M3*M4*M5), (M1*M2)*(M3*M4*M5),
(M1*M2*M3)*(M4*M5), and (M1*M2*M3*M4)*M5.
Using equation (B) written above, both of the 2 products M1*(M2*M3*M4*M5) and (M1*M2*M3*M4)*M5
can be parenthesized in 5 different ways.
Using equation (A) written above, both of the 2 products (M1*M2)*(M3*M4*M5) and
(M1*M2*M3)*(M4*M5) can be parenthesized in 2 different ways.
Accordingly, P(5) = P(4) + P(3) + P(3) + P(4) = 5+ 2 + 2+ 5 = 14 (C)
Finally, suppose that we have 6 matrices named M1, M2, M3, M4, M5 and M6. Then, the product of
M1*M2*M3*M4*M5*M6 can be split at 5 different positions: M1*(M2*M3*M4*M5*M6),
(M1*M2)*(M3*M4*M5*M6), (M1*M2*M3)*(M4*M5*M6), (M1*M2*M3*M4)*(M5*M6), and
(M1*M2*M3*M4*M5)*M6.
Using equation (C) written above, both of the 2 products M1*(M2*M3*M4*M5*M6) and
(M1*M2*M3*M4*M5)*M6 can be parenthesized in 14 different ways.
Using equation (B) written above, both of the 2 products (M1*M2)*(M3*M4*M5*M6) and
(M1*M2*M3*M4)*(M5*M6) can be parenthesized in 5 different ways.
Using equation (A) written above, the product (M1*M2*M3)*(M4*M5*M6) can be parenthesized in 2*2 = 4
different ways.
Page 12 of 13
Accordingly, P(6) = P(5) + P(4) + 2*P(3) + P(4) + P(5) = 14 + 5 + 4 + 5 + 14 = 42
Therefore, the number of different ways to parenthesize the product of the 6 matrices is 42.
We can verify the number of different ways to parenthesize the product of the 6 matrices (42 ways) using the
Catalan number Cn that is given by:
1
Cn = 𝑛+1 (2𝑛
𝑛
) [ where n+1 is the number of matrices ]
In our case, we have n+1 = 6, or n=5.
Accordingly, C5 is given by:
1 1 10!
C5 = 5+1 (10
5
)= = 42
6 5! ∗ (10−5)!
B. Experimental part
Unfortunately, I didn’t manage to allocate enough time to complete this part of the problem
Page 13 of 13
