Description
Problem 1 [DPV] Problem 6.1 – Maximum sum
A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S…
(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….
(b) State recurrence for entries of table in terms of smaller subproblems.
2
Name: 3
(c) Write pseudocode for your algorithm to solve this problem.
(d) Analyze the running time of your algorithm.
3
Name: 4
Problem 2 [DPV] Problem 6.8 – Longest common substring
Given two strings x = x1x2 . . . xn and y = y1y2 . . . ym we wish to find the length of their longest
common substrings…
(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….
(b) State recurrence for entries of table in terms of smaller subproblems.
4
Name: 5
(c) Write pseudocode for your algorithm to solve this problem.
(d) Analyze the running time of your algorithm.
5
Name: 6
Problem 3 [DPV] Problem 6.19 – Making change k
Given an unlimited supply of coins of denominations x1, x2, …, xn, we wish to make change for a
value v using at most k coins…
(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….
(b) State recurrence for entries of table in terms of smaller subproblems.
6
Name: 7
(c) Write pseudocode for your algorithm to solve this problem.
(d) Analyze the running time of your algorithm.
7
Name: 8
Problem 4 (The thief ’s plan)
A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The
houses are labeled 1, 2, . . . , n and the thief will address then sequentially. The thief has an estimate
of the profit to be earned from burglarizing each house pi
, i = 1 . . . n, where pi > 0. To avoid detection, he decides that he will never burglarize two adjacent houses, meaning that if he burglarize
house 2, he cannot burglarize house 1 or house 3. Design a dynamic programming algorithm to
determine the maximum total profit he can achieve.
Example: In each of the following two neighborhoods, the maximum achievable profit is $100:
Case 1: p = [$20, $100, $30].
Case 2: p = [$40, $30, $10, $60].
Your input is the list [p1, p2, . . . , pn]. Your output should be the maximum profit the thief can
get. You don’t have to return the list of houses the thief has to burglarize to achieve the maximum.
(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….
(b) State recurrence for entries of table in terms of smaller subproblems.
8
Name: 9
(c) Write pseudocode for your algorithm to solve this problem.
(d) Analyze the running time of your algorithm.