Week 5 Studio Sheet (Solutions)
Useful advice: The following solutions pertain to the theoretical problems given in the tutorial classes. You are strongly advised to attempt the problems thoroughly before looking at these solutions. Simply reading the solu- tions without thinking about the problems will rob you of the practice required to be able to solve complicated problems on your own. You will perform poorly on the exam if you simply attempt to memorise solutions to the tutorial problems. Thinking about a problem, even if you do not solve it will greatly increase your understanding of the underlying concepts. Solutions are typically not provided for Python implementation questions. In some cases, psuedocode may be provided where it illustrates a particular useful concept.
Assessed Preparation
Problem1. Implementthesolutiontothecoinchangeproblemdescribedinthelectures.Yoursolutionshould
return the number of coins needed, along with how many of each denomination are required. (a) Usethebottom-upstrategytocomputethesolutions
(b) Usethetop-downstrategytocomputethesolutions
Consult the notes if you are unclear on the difference between the two approaches.
Problem 2. Suppose that you are a door-to-door salesman, selling the latest innovation in vacuum cleaners to less-than-enthusiastic customers. Today, you are planning on selling to some of the n houses along a particular street. You are a master salesman, so for each house, you have already worked out the amount ci of profit that you will make from the person in house i if you talk to them. Unfortunately, you cannot sell to every house, since if a person’s neighbour sees you selling to them, they will hide and not answer the door for you. Therefore, you must select a subset of houses to sell to such that none of them are next to each other, and such that you make the maximum amount of money.
For example, if there are 10 houses and the profits that you can make from each of them are 50, 10, 12, 65, 40, 95, 100, 12, 20, 30, then it is optimal to sell to the houses 1, 4, 6, 8, 10 for a total profit of $252. Devise a dynamic programming algorithm to solve this problem, i.e. to return the maximum profit you can obtain.
(a) DescribeinplainEnglish,theoptimalsubstructurepresentintheproblem
(b) Defineasetofoverlappingsubproblemsthatarebasedontheoptimalsubstructure (c) Whatarethebasecasesubproblemsandwhataretheirvalues?
(d) Writearecurrencerelationthatdescribesthesolutionstothesubproblems
(e) Writepsuedocodethatimplementsallofthisasadynamicprogrammingalgorithm.
Let the houses on the street be numbered from 1 to n from left to right. We begin by observing that the constraint that we cannot sell to the neighbours of a house is equivalent to the constraint that if we sell to house i , then we cannot sell to house i − 1 (it is not necessary to explicitly prevent ourselves from selling to house i +1, since if we sell to house i +1, then they will not allow us to sell to house i).
Suppose that we find ourselves in front of house i , deciding whether we should sell to it. If we do decide to sell to it, then we cannot have sold anything to house i − 1, but we are allowed to sell to a valid subset of houses from 1 to i −2. If we do not decide to sell to house i, then any valid subset of houses from 1 to i − 1 is acceptable to sell to.
The optimal substructure of the problem can then be observed as follows. Suppose that house i is the last house that we will consider selling to. If we chose to sell to house i , then we cannot sell to house i − 1, and must therefore sell to the houses [1..i − 2], and we must do this in a way that makes us the maximum profit. If we decide not to sell to house i , then we must sell to the houses [1..i − 1] in such a way that we make maximum profit.
Let us therefore define our subproblems to be
DP[i ] = {the maximum profit that we can make from selling to a subset of the houses [1..i ]}
for all 1 ≤ i ≤ n. When there is just a single house, we should sell to it, so a suitable base case is DP[1] = c1. We leverage the optimal substructure to write the recurrence
DP[i − 1], (if we decide not to sell to house i ), DP[i]=max DP[i −2]+ci, (ifwedecidetoselltohousei) .
for all 2 ≤ i ≤ n , where we define DP[0] = 0 (the profit we can make by selling to the empty set of houses). The optimal solution to the problem is the value of DP[n ].
An bottom-up implementation of this algorithm might look like this.
1: functionSALESMAN(c[1..n])
2: Set DP[0..n] = 0
3: DP[1] = c1
4: fori=1ton do
5: DP[i]=max(DP[i −1],DP[i −2]+ci)
6: end for
7: return DP[n ]
8: endfunction
Studio Problems
Problem3. ExtendyoursolutiontoProblem2sothatitreturnsanoptimalsubsetofhousestosellto,inaddition
to the maximum possible profit.
To reconstruct the optimal set of houses, we make the observation that in a range of houses [1..i ], house i isoptimaltoselltoifDP[i]>DP[i−1]. Whyisthistrue? IfDP[i]>DP[i−1],thensinceDP[i]=max(DP[i− 1],DP[i−2]+ci)>DP[i−1],itmustbetruethatDP[i]=DP[i−2]+ci >DP[i−1].Inotherwords,itismore profitable to sell to house i than to not. Using this observation, a simple backtracking procedure could work as follows:
1: functionSALESMAN(c[1..n])
2: Set DP[0..n] = 0
3: DP[1] = c1
4: fori=1ton do
5: DP[i]=max(DP[i −1],DP[i −2]+ci)
6: end for
7: Set houses = []
9: whilei >0do
10: if DP[i] > DP[i −1] then
11: 12: 13: 14: 15: 16: 17: 18:
houses.append(i )
i=i−2 else
i=i−1 end if
return DP[n], houses endfunction
Note that we subtract 2 from i if we decide to include house i , so that we cannot accidentally sell to house i − 1 as well, otherwise we subtract 1.
Problem 4. You find yourself curiously stranded on an n × n grid, unsure of how you got there, or how to leave. Some of the cells of the grid are blocked and cannot be walked through. Anyway, while you’re here, you decide to solve the following problem. You are currently standing at the bottom-left corner of the grid, and are only able to move up (to the next row) and to the right (to the next column). You wonder, how many ways can you walk to the top-right corner of the grid while avoiding blocked cells? You may assume that the bottom-left and top-right cells are not blocked. For example, in the following grid, the answer is 19.
Write a dynamic programming algorithm that given a grid as input, counts the number of valid paths from the bottom-left cell to the top-right cell. Your algorithm should run in O(n2) time.
Let’s denote the bottom-left corner as cell (1,1) and the top-right corner as cell (n,n). Suppose that you are standing in cell (i , j ). In general, you have two choices, to move to cell (i + 1, j ) or to move to cell (i,j+1). Letp1 andp2 denotethenumberofpathsfromcell(i+1,j)tocell(n,n)andthenumberof paths from cell (i , j + 1) to cell (n , n ) respectively. These paths must all be different, since paths from the first set use cell (i + 1, j ), and those from the second use (i , j + 1), and a valid path cannot contain both of these (think about why this is true). Hence the total number of paths from cell (i , j ) to cell (n , n ) is just p1 +p2.
The edge/base cases are if cell (i , j ) is blocked, then there are no paths from it, or if you are currently on the top row (i = n) or rightmost column (j = n), in which case you only have one cell that you can move to. Finally, the last base case is that the number of paths from cell (n,n) to cell (n,n) is just 1. Let’s write a dynamic programming algorithm along these lines.
Let’s denote by DP[i , j ], the following subproblems:
DP[i,j]={The number of valid paths from cell (i,j) to cell (n,n).}
for all 1 ≤ i , j ≤ n . Then we can write the following recurrence:
DP[i,j]= DP[i,j+1]
DP[i + 1, j ]
DP[i +1, j]+DP[i, j +1]
if (i , j ) = (n , n )
if (i , j ) is blocked if i = n
if j = n otherwise
The value of DP[1, 1] is the solution. There are a total of n 2 subproblems, and each of them can be evalu- ated in constant time, hence the time complexity of this algorithm will be O(n2).
Problem 5. You somehow find yourself on yet another n × n grid, but this time, it is more exciting. Each cell of the grid has a certain non-negative amount of money on it! Denote the amount of money in the cell of row i , column j by ci , j . You are standing on the bottom-left corner (1, 1) of the grid. From any cell, you can only move up (to the next row), or right (to the next column). What is the maximum amount of money that you can collect?
Givenci,j foreverycell,describeadynamicprogrammingalgorithmtosolvethisproblem.Youralgorithmshould run in O(n2) time.
This problem is very similar to Problem 4. If we are standing in cell (i , j ), then we have two choices, to move up to cell (i +1, j) or to move right to cell (i, j +1). We should select the best of the two, whichever leads to a greater amount of money. This motivates the following subproblems:
DP[i , j ] = {The maximum amount of money we can make starting from cell (i , j )}
The recurrence must take into account the boundary cases (if we are in the top row or rightmost column, we only get one choice) and the base case (if we are in cell (n , n ) we are finished and can’t move anywhere else). The following recurrence captures these ideas:
DP[i,j]=ci,j +
DP[i + 1, j ]
DP[i , j + 1]
max(DP[i , j + 1], DP[i + 1, j ])
if (i , j ) = (n , n ) if j = n
if i = n otherwise
The optimal solution is the value of DP[1, 1]. There are n 2 subproblems, and each takes constant time to solve, so the solution takes O(n2) time.
Problem 6. Consider a sequence a1,a2,…,an of length n. A subsequence of a sequence a is any sequence that can be obtained by deleting any of the elements of a . Devise a dynamic programming algorithm that finds the length of a longest increasing subsequence of a . That is, a longest possible subsequence that consists of elements in strictly increasing order. Your algorithm should run in O(n2) time.
For example, given the sequence {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, the longest increasing subsequence is {0, 2, 6, 9, 11, 15} of length 6 (shown in bold in the original sequence).
Consider a particular sequence a1,a2,…an and a longest increasing subsequence of it, say aj1 ,aj2 ,…,ajk , where j1, j2,…, jk represent the indices of the elements of a that are part of the subsequence. Consider
now some prefix of the subsequence, say a j1 , a j2 , …, a jk −1 . The key observation is that it must be the case that of all subsequences of a that end with the element at position jk−1, this one is the longest. If it were not, then we could replace the prefix of our proposed longest increasing subsequence with a longer one. In other words, the prefixes of a longest increasing subsequence are themselves longest increasing subsequences that end at a particular earlier element. This suggests the following subproblems for a dynamic programming approach:
DP[i ] = {The length of the longest increasing subsequence that ends with the element at position i },
for 1 ≤ i ≤ n. To find the longest increasing subsequence that ends with the element at position i, we need to figure out what its prefix could have been. Since the sequence must be increasing, this is simple, the prefix could be any subsequence that ends with an element a[j] such that a[j] < a[i] (so that we maintain the increasing property). So, let’s just try all of the preceding elements and pick the best one.
0max ifa[i]≤a[j]forall j