[Solved] EE4371-Assignment3a Stacks, Recursion

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 w_i 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 10⁴ N (uniform in 1 to 20), W (uniform in 0 to N²/2) and the w_i 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:

• 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?