Homework 14

General Comments

• For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You can get up to 50% credit on a problem if you get significant outside assistance. Thus, if you are totally stuck on a problem it might be worth getting help. However, you must indicate any assistance/collaboration (See the Homework Assistance section on the Policies page). Failure to do so could result in a failing grade for the course! Note that getting help from the Help Center or me does not count as significant outside assistance, but talking with your classmates or searching on the Internet does!
  
• If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

Details

1. (8) IDAA Problem 7.2 #2. Make sure you show all steps of your computation.
2. (6) This problem (based on 8.1): Solve this instance of the coin row problem: 6, 2, 3, 9, 11, 8, 5. Don't forget to give the coins in the optimal solution!
3. (4+2+2) Consider this instance of the knapsack problem.
   Capacity W = 11
   Item weight value
   1 3 27
   2 2 13
   3 4 40
   4 3 32
   5 5 48
   6 7 82
   7 1 12
   
   1. Solve this instance of the knapsack problem using the bottom-up dynamic programming algorithm. Give the optimal cost and a list of the items to take.
   2. How many different optimal solutions does this instance have? Explain how you know.
   3. In general, how can you determine whether or not there is a unique solution to the knapsack problem using the table constructed by the algorithm?
4. (4+2+2)
   1. Solve the instance of the knapsack problem from #1 using the memory function method.
   2. Indicate which entries in the table are never computed by placing a '-' instead of a number.
   3. Clearly indicate (using a circle or square or highlighter) which cells of the table are looked up rather than being recomputed. (That is, the entries that WOULD be computed a second time if the standard recursive algorithm was used.)