Computer Science 409: Homework 9

Homework 9: Handed out: 4/19/01; Due: 4/26/01

Section      Number   Points    Comments
27.1 	      6 	3 	Prove that it satisfies the properties it does satisfy,
		        	and give a counterexample to any property it doesn't satisfy
27.2 	      2 	3
27.2 	      3 	4
27.2 	      7 	4
16.1 	      1 	5 	Fill in the m[i,j] and s[i,j] tables as in the algorithm
				and then write a parenthesization such as ((A1 A2)((A3 A4)(A5) A6)))
Problems     16-3 	9 	This is one of the supplementary problems on p. 325
17.2 	      1 	4
17.2 	      2 	8 	[Hint: let c[i,w] be the value of the best solution if you can 
				put only items 1, ..., $i$ and have maximum weight w.]
17.2 	      4 	4
36.1 	      3 	6