CSE 441T/541T Hints for HW 2 practice problems

Problem 1

The easiest general subproblem form is the problem of making change for i cents.

Problem 2

Either you can work from the front which leaves you the general subproblem form of finding the best alignment of the suffix i...n1 of D1 with the suffix j...n2 of D2.

Or you can work from the back which leaves you the general subproblem form of finding the best alignment of the prefix 1...i of D1 with the prefix 1...j of D2.

Problem 3

Any of the four general subproblem forms would work. I think the first two are easier to work with.

Option 1: The general subproblem is to find the cost of the best solution from post i to post n. The answer for the original problem is when i=1.

Option 2: The general subproblem is to find the cost of the best solution from post 1 to post i. The answer for the original problem is when i=n.

Option 3: The general subproblem is to find the cost of the best solution from post i to post n where you cannot exchange your canoe until at least post j. The answer to the original problem is when i=1 and j=2.

Option 4: The general subproblem is to find the cost of the best solution from post 1 to post i where the latest post when you can exchange your canoe is post j. The answer to the original problem is when i=n and j=n-1.

Problem 4

Either of the follwoing two general subproblem forms will work. You can also create variants where you create some non-boolean cost but there is no need to do this.

Option 1: The general subproblem is to determine if x[i],...,x[m] and y[j],....,y[n] can interleave to form z[i+j],...,z[n+m]. The answer to the original problem is when i=1 and j=1.

Option 2: The general subproblem is to determine if x[1],...,x[i] and y[1],....,y[j] can interleave to form z[i],...,z[i+j]. The answer to the original problem is when i=m and j=n.

Return to the CSE 441T/541T Home Page