Description
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 {wi} N−1 i=0 , 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 N 2/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?
