From:	Patrick Prosser
Sent:	20 January 2011 23:11
To:	Patrick Prosser
Subject:	knapsack ... and why it is nice
Attachments:	KnapSack.java; ks01.txt

It is nice because we can show:
  
 - KS follows on from Power Set
 - it is a problem that is hard for a human
   - the computer looks intelligent
 - by varying the input we can see non-polytime behaviour

NOTE: there is an effect, a random effect, possibly due to the HashSet order 
being non-deterministic between runs. This may be due to hashing using some 
machine state. And this is also interesting.

This would be nice material for examples class: give students the problem and 
ask for a solution, show program run, then explain how it did it.


--
Patrick Prosser                     tel:  +44 141 330 4934
Computing Science               fax: +44 141 330 4913
University of Glasgow           web: http://www.dcs.gla.ac.uk/~pat/
Glasgow G12 8RZ              email: pat@dcs.gla.ac.uk