Discussion 6
1. You are to compute the total number of ways to make a change for a given amount m. Assume that we have an unlimited supply of coins and all denominations are sorted in ascending order:1 = d1 < d2 < ... < dn . Formulate the solution to this problem as a dynamic programming problem.
Solution:
We will define COUNT(n, m) as the total number of ways to make change for amount m using coin denominations 1 to n.
The recurrence formula will be:
COUNT(n,m) = COUNT(n-1, m) + COUNT(n, m- dn)
Note: COUNT(n-1, m) is the number of ways to make change for amount m without using coin denomination n. And COUNT(n, m- dn) represents the number of ways to make change for amount m using at least one coin of denomination n.
Initialization:
COUNT (i,0) = 1 for 0 < i ¡Ü n since there is a way to pay the amount 0 (by paying 0 of all coin types)
COUNT(0,j) = 0 for 0 < j ¡Ü m since there is no way to pay a non-zero amount without any coins
Bottom up pass: For i = 1 to n
For j = 1 to m
COUNT(n,m) = COUNT(n-1, m)
If ( m - dn ¡Ý 0 ) COUNT(n,m) = COUNT(n,m) + COUNT(n, m- dn)
Endfor Endfor
The total count will be at COUNT(n,m)
This will take O(mn) which is pseudopolynomial since m is the numerical value of an input term.
2. Graduate students get a lot of free food at various events. Suppose you have a schedule of the next n days marked with those days when you get a free dinner, and those days on which you must acquire dinner on your own. On any given day you can buy dinner at the cafeteria for $3. Alternatively, you can purchase one week's groceries for $10, which will provide dinner for each day that week (that day and the six that follow). However, because you don't have a fridge, the groceries will go bad after seven days (including the day of purchase) and any leftovers
must be discarded. Due to your very busy schedule, these are your only two options for dinner each night. Your goal is to eat dinner every night while minimizing the money you spend on food.
Solution:
We will define OPT(i) as the minimum cost of dinner for days 1 to i.
The recurrence formula will be:
OPT(i-1) if there is free food on day i
OPT(i) =
Otherwise, Min( OPT(i-1) + 3 , OPT(i-7) + 10 )
Initialization:
We need to initialize OPT(0..6). These are trivial problems to solve.
Bottom up pass: For i = 7 to n
If Free(i) then
OPT(i) = OPT(i-1)
Else
OPT(i) = Min( OPT(i-1) + 3 , OPT(i-7) + 10 )
Endif Endfor
The minimum cost of dinner will be at OPT(n).
This will take O(n) which is polynomial if we assume that the input consists of an array of size n called Free() where Free(i) is true when there is free food on day i, and false otherwise.
To be able to determine the dinner schedule, we will go top down:
i=n While i > 0
If then
Free(i) Mark up the calendar with ¡°free food¡± on day i i=i-1
Else if OPT(i-1) + 3 < OPT(i-7) + 10 then
Mark up the calendar with ¡°cafeteria¡± on day i i=i-1
Else
Mark up the calendar with ¡°go grocery shopping¡± on day i-6 Mark up the calendar with ¡°eat at home¡± on days i-5 to i
i=i-7 Endif
Endwhile
Note: on the day we ¡°go grocery shopping¡± we also ¡°eat at home¡±.
The top down pass will also take O(n) time. So the whole solution runs in O(n) time.
3. You are in Downtown of a city and all the streets are one-way streets. You can only go east (right) on the east-west (left-right) streets, and you can only go south (down) on the north-south (up-down) streets. This is called a Manhattan walk.
a) In Figure A below, how many unique ways are there to go from the intersection marked S (coordinate (0,0)) to the intersection marked E (coordinate (n,m))?
Formulate the solution to this problem as a dynamic programming problem. Please make sure that you include all the boundary conditions and clearly define your notations you use.
Solution:
Let¡¯s say E is at coordinates (0,0) and s is at coordinates (n,m).
We will define COUNT(n, m) as the total number of ways to go from coordinates (n,m) to (0,0).
The recurrence formula will be:
COUNT(i,j) = COUNT(i, j-1) + COUNT(i-1, j)
Initialization:
COUNT (i,0) = 1 for 0 < i ¡Ü n since there is only one way to go (horizontally) from (i,0) to (0,0) COUNT (0,j) = 1 for 0 < j ¡Ü n since there is only one way to go (vertically) from (0,j) to (0,0)
Bottom up pass: For i = 1 to n
For j = 1 to m
COUNT(i,j) = COUNT(i, j-1) + COUNT(i-1, j) Endfor
Endfor
The total count will be at COUNT(n,m)
This will take O(mn) which is pseudo-polynomial if we assume that the input only consists of the coordinates n and m. If the input consisted of the 2D array of all intersections, then the run time will be polynomial.
b) Repeat this process with Figure B; be wary of dead ends.
We can use the same approach and recurrence formula as in part a, except that we need to apply special recurrence formulae to the intersections that are affected namely (2, 2) and (3, 2). So, the implementation will be modified like this:
Bottom up pass: For i = 1 to n
For j = 1 to m
If (n=2 and m=2) then
Endfor Endfor
COUNT(i,j) = COUNT(i-1, j) Else if (n=3 and m=2) then
COUNT(i,j) = 0 Else
COUNT(i,j) = COUNT(i, j-1) + COUNT(i-1, j) Endif