Assignment #7 CMPUT 204

Assignment #7
(Total 40 marks)
CMPUT 204
Some questions here are based on Problem Set #5 and our lecture notes. Discussions of related problems
may also be found online. You may consult, adopt, or revise any of these solutions to compose your answers.
But recall that you must understand what you submitted and be able to explain your answers. If your
algorithm is the same as the one given in the Problem Set or lecture notes, just indicate so; otherwise
please specify.
Problem 1. (15 marks)
a. (5 marks) Consider the 0-1 knapsack problem for items i = 1,2,3,4,5, whose values are [4, 3, 6, 5, 7]
and whose weights are [2, 2, 3, 4, 5]. Assume the knapsack capacity is 10. Apply the knapsack algorithm
discussed in class to the problem by filling the 2-dimensional table A[i, D] (0 ≤ i ≤ 5, 0 ≤ D ≤ 10), and
apply the Print-Opt-Knapsack procedure to show which items are in your optimal solution.
Partial Solution: The table A[i, D] below is partially filled, and you are to fill the remaining cells.
i \D 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4
2 0 0 4 4 7 7 7
3 0 0 4 6 10 13
4 0 0 4 6 10 10
5
b. (5 marks) Find an LCS of strings “ABAECCD” and “ACDEF”. You should show how you derived
your solution using a table similar to Fig. 15.8 of CLRS p395.
c. (5 marks) Matrices A, B, C, D, E have respective dimensions 1 × 5, 5 × 2, 2 × 6, 6 × 1, 1 × 4. What
is the minimum number of scalar multiplications needed to compute A × B × C × D × E? Give the
parenthesization of matrices that yields this number. Show how you arrived at your answer.
Problem 2. (8 marks)
In this question, you are asked to show how a problem instance is solved for the following problem
given in Problem Set #5.
There are n Hudson’s Bay Company posts on the River Koksoak. At any of these posts you can rent a
canoe to be returned at any other post downstream (it is next to impossible to paddle against the current.)
For each possible departure point i and each possible arrival point j the company’s tariff gives the cost of
a rental between i and j which is C[i, j]. However, it can happen that the cost of renting from i to j is
higher than the total cost of a series of shorter rentals, in which case you can return the first canoe at some
post k between i and j and continue the journey in a second canoe. There is no extra charge for canoe
change. Give an efficient algorithm to determine, given n and costs C[i, j], the sequence of canoe rentals
with minimum cost for a trip from post 1 to post n.
ˆ In this question, you are asked to fill the tables A[i] and S[i] (1 ≤ i ≤ 6) as defined above for the
following problem instance:
1
C[1, 2] = 7, C[1, 3] = 8, C[1, 5] = 21
C[2, 3] = 5, C[2, 5] = 13
C[3, 4] = 5, C[3, 5] = 9, C[3, 6] = 17
C[4, 5] = 8, C[4, 6] = 15
C[5, 6] = 7
For all other pairs of i < j, C[i, j] = ∞, which means renting from i to j is not available. For
part marks, we’d like to understand how you did your work. For this purpose, please explain how
you filled the cells at A[5] and A[6].
ˆ According to S[.], which rental arrangement yields the minimum cost?
Problem 3. (17 marks)
Longest Sub-Palindrome problem: given a sequence X = hx1, ..., xni find the longest subsequence
hxi1
, ..., xik
i such that ij < ij+1 for any j, and that is a palindrome: k is even and the inverse sequence
hxik
, xik−1
, ..., xi1
i is identical to the original sequence hxi1
, ..., xik
i. (E.g., “abba” is a sub-palidrome of
“tablebrand.”) Note that the definition here differs slightly from the standard dictionary definition of
palindrome; here we only consider palindromes whose length is an even number.
In this question, you are asked to present a complete solution to demonstrate all the ingredients of
solving this problem by DP.
a. Denote the problem by LSP(x1, ..., xn). Give a recursive definition to solve the problem. Argue that
all of the recursive calls live in a small domain so that the DP approach is possible.
b. Turn your recursive definition to a table definition. Indicate the dimensions of your table, what each
cell of your table stores, and which cell stores the value of an optimal solution (the value is the
number of characters in a longest sub-palindrome of the given string).
c. Give an algorithm in pseudocode to compute (the value of) an optimal solution. Analyze its running
time.
d. Give an algorithm in pseudocode to generate the actual string of an optimal solution. Comment on
its running time.
e. Now consider the input string S = hp, e, q, q, d, ei.
(i) Draw the table according to your solution, and for each cell fill its value.
(ii) According to your algorithm, which sub-palindrome is generated? Explain briefly how it is
generated.
2