Description
1. [30%] You are given a 0-1 knapsack problem where the capacity of the knapsack W = 30 and the
set of items S = {(i1, 5, $50), (i2, 20, $140), (i3, 10, $60)} where each element in set S is a tuple of
(item ID, weight, profit). Solve the given 0-1 knapsack problem using the dynamic programming
method discussed in Chapter 12. Clearly show every step.
2. [40%] A set {3, 4, 5, 6} is given. For the set, find every subset that sums to S = 13.
a. [10%] Solve the problem using the depth first method. Draw a state space tree and
clearly show every step. Also, number the nodes in the sequence of visiting them.
b. [30%] Find the subsets via backtracking. Draw a (pruned) state space tree and clearly
show every step. Number the nodes in the sequence of visiting them too.
3. [30%] When the capacity of the knapsack is 16, solve the following 0-1 knapsack problem using
the backtracking algorithm discussed in class that uses the optimal fractional knapsack algorithm
to compute the possible upper bound of the profit.
i pi wi pi / wi
1 $10 5 $2
2 $30 5 $6
3 $40 2 $20
4 $50 10 $5
4. [20%] Assume that a hash table has 17 buckets where each bucket has only one slot. A simple
hash function: home bucket = key % 17 (where % is a mod function) is used to compute the
home bucket based on the key. You are supposed to insert the following keys to the hash table:
6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45 using the following overflow handling methods.
(1) Use the linear probing (linear open addressing) method to handle overflows, if any.
(2) Use the sorted chaining method to deal with overflows, if any.
CS575
