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.
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.
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.
b) Repeat this process with Figure B; be wary of dead ends.
Assume you want to ski down the mountain. You want the total length of your run to be as long as possible, but you can only go down, i.e. you can only ski from a higher position to a lower position. The height of the mountain is represented by an n X n matrix A. A[i][j] is the height of the mountain at position (i,j). At position (i,j), you can potentially ski to four adjacent positions (i-1,j) (i,j-1), (i,j+1), and (i+1,j) (only if the adjacent position is lower than current position). Movements in any of the four directions will add 1 unit to the length of your run. Provide a dynamic programming solution to find the longest possible downhill ski path starting at any location within the given n by n grid.
1200 1000 1200 1500 1100 1600 2000 1900 1200 1700 1900 2300 1000 1500 2000 2450 1100 1500 1800 2200 1100 1000 1500 1800 1000 1000 1200 1300 900 800 1000 1200
1700 1500 1000 1000 1800 1600 1200 1250 2400 2000 1900 1750 2600 2100 2000 1500 2300 2200 2100 1600 2100 1900 2000 1700 1700 1900 1900 1800 1500 1900 2000 2100
Imagine starting with the given decimal number n, and repeatedly chopping off a digit from one end or the other (your choice), until only one digit is left. The square-depth SQD(n) of n is defined to be the maximum number of perfect squares you could observe among all such sequences. For example, SQD(32492) = 3 via the sequence
32492 → 3249 → 324 → 24 → 4
since 3249, 324, and 4 are perfect squares, and no other sequence of chops gives more than 3
perfect squares. Note that such a sequence may not be unique, e.g. 32492 → 3249 → 249 → 49 → 9
also gives you 3 perfect squares, viz. 3249, 49, and 9.
Describe an efficient algorithm to compute the square-depth SQD(n), of a given number n, written as a d-digit decimal number 𝑎𝑎1𝑎𝑎2 ... 𝑎𝑎𝑑𝑑. Analyze your algorithm’s running time. Your algorithm should run in time polynomial in d. You may assume the availability of a function IS_SQUARE(x) that runs in constant time and returns 1 if x is a perfect square and 0 otherwise.
IS_Square() is a function that returns a 1 if the number passed to it is a perfect square and returns 0 otherwise.