Description
- Read Chapter 3 of Tanenbaum
- Read Chapter 2 of Aho, Hopcroft and Ullman
- Consider the knapsack problem in Aho:
Given a set of objects with weights, we need to select a subset of these objects so that their total weight is exactly W. W and wi are positive integers, and N is given.
(a) Following the pseudocode below from Aho, write the C code to implement this problem.
Boolean knapsack(int W,int i){ if W==0
return True
else if W<0 or i>=N
return False
else if knapsack(W-w[i],i+1)
print w[i] return True
else return knapsack(W,i+1)
end }
- Use a static scalar integer, count, to accumulate the number of times knapsack is called.
- Write a main program that randomly generates 104 N (uniform in 1 to 20), W (uniform in 0 to N2/2) and the wi values (uniformly random in 0 to N). For each such set, determine the number of times knapsack was called. Write out a table as follows:
| N | Min | Max |
| 1 | 1 | 1 |
| … | … | … |
| 20 | ? | ? |
- In the report, include the output of Min and Max vs N shown above. Determine the scaling (is it logarithmic, polynomial (if so order), or exponential (exponent?)) Can you justify the scaling?
