## Description

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