1. Read Chapter 3 of Tanenbaum
2. Read Chapter 2 of Aho, Hopcroft and Ullman
3. 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 }
(a) Use a static scalar integer, count, to accumulate the number of times knapsack is called.
(b) 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
?
?
(c) 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?
