CSCI 385 Spring 2023
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 4

Details

  1. (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?
  2. (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.)
  3. IDAA 8.4.7 (page 312) (6)
    Show all of the intermediate matrices!