Homework 3 - Dynamic Programming, Part 1
The homework is due at the start of class on Tuesday, March 31.
Please write your dynamic programming solutions in the following form:
- Part (a), define the entries of the table in words,
-
e.g., T(i) = min cost subsequence of items a1,...,ai
or
T(i,j) = TRUE if there is a subsequence of items a1,...,ai which sums to j,
-
and FALSE otherwise.
-
Part (b), state the recurrence for the entries of your table,
and, if necessary, explain in words why it's true.
-
Part (c), state pseudocode for filling the table,
and
-
part (d), analyze the running time.
Homework problems:
-
Max contiguous subsequence: [DPV] Problem 6.1.
- Hotel stops: [DPV] Problem 6.2.
- Yuckdonald's: [DPV] Problem 6.3.
- Dictionary: [DPV] Problem 6.4.