Lecture outline for Week 6

I. Fundamental algorithm techniques
	- greedy method
		- at each step, pick the optimal choice and the result
		  yields the optimal solution
	- divide and conquer
		- break the problem into pieces, solve each individual piece,
		  and combine the pieces together
		- ex: sorting
	- dynamic programming
		- we maintain a table of intermediate values
		- like divide&conquer, we break problem into subproblems

II. The knapsack problem
	- We have a sack with a weight limit K.
	- We have n items, each has a value (v_i) and a weight (w_i).
	- We want to maximize the value of the material we carry home.
	- Suppose we can take a fraction of an item (ex: gold dust)
	- Formalize the problem:
		maximize Sum(frac_i * v_i) such that frac_i * w_i <= K.
		where frac_i is in the range [0, 1]
	- Greedy solution:
		- assume items are sorted by nonincreasing (v_i/w_i)
		- while there is still room in the sack, add as much of item
		  i as possible, then increment i
	- why is this greedy?
		- at each step we are adding the optimal item
			-i.e. the item with greatest value/weight
		- this leads to an optimal solution
			- proof, assume it doesn't.
			- then we have another set of fractions which yields
			  a better total, call these greedy vs. optimal
			- consider sorted items & the first item with different
			  fractions.  
			- greedy must have picked more of this item than
			  optimal
			- increase weight of this item picked and decrease
			  weight of least item in optimal, as sorted by greedy
			- result solution is optimal - cost_j + cost_i and
			   cost_i >= cost_j
	- Now assume we cannot split items (ex: paintings)
		- thus frac_i is 0 or 1
	- formal problem:
		maximize Sum(frac_i * v_i) such that frac_i * w_i <= K
		where frac_i is 0 or 1
	- will greedy work?
		consider K = 10, objects with weights: 6, 5, 5
		and values: 12, 8, 7
	- try all possible combinations of objects and pick the one with 
	  greatest value such that it fits in sack
		- will work but is computationally expensive -> 2^n combinations
	- consider breaking the problem into pieces:
		- let Knap(K, {1, ..., n}) be the maximum value of a sack
		  with capacity K and items 1 through n.
		- note that we either take item n or we don't, thus
		  Knap(K, {1...n}) = max{v_n + Knap(K-w_n, {1...n-1}),
					 Knap(K, {1...n-1})}
		- do we need to consider all possible combinations when
		  computing Knap(K, {1...n-1})?
			- no, only a solution which has an optimal answer
			- suppose we had the optimal solution for
			  Knap(K, {1...n}), the optimal solution includes item
			  n, but the optimal solution includes a sub-optimal
			  solution to Knap(K-w_n, {1...n-1})
			- note that both the suboptimal and the optimal solution
			  to the subproblem have weight <= K-w_n.
			- thus we can remove the suboptimal solution to
			  Knap(K-w_n, {1...n-1}, replace it with the optimal
			  solution to the subproblem and the result is 
			  a solution with greater value for Knap(K, {1...n}).
			- but we assumed that we had the best solution for
			  Knap(K, {1...n}).
			- thus, we only need to consider the optimal solution
			  to each subproblem
		- how many steps (measured by function calls) are needed to
		  compute Knap(K, {1...n}) by the above formula?
			- 2^n - 1, still too many
		- but many of the function calls are solving the same problem
		  over and over again.
		- rather than resolve the same problem, let us store the 
		  values in a table and compute "from the bottom up".
	- create a table T with n rows and K columns
		- T[i][j] will store the maximum value Knap(j, {1...i}).
		- thus T[i][j] = max{v_i+T[i-1][j-w_i], T[i-1][j]}
		- how many steps are needed to solve the problem
			- as many as it takes to fill in the table, Kn
			- the final solution is in T[n][K]
		- we may also need to store an indicator with each table
		  entry so that we can reverse our steps through the table
		  and find the optimal combination
			- it is not enough just to know the optimal value,
			  we also want to know which objects we should take

III. Dynamic Programming
	- we store the intermediate values of the algorithm in a table so
	  that we can look them up as we need them
	- greedy method vs. dynamic programming
		- greedy: works when the optimal solution to any subproblem
		    will lead to the optimal solution of the whole problem
		- dynamic programming: works when the optimal solution to
		    some subproblem leads to the the optimal solution of the
		    whole problem
			- thus we need to generate all the necessary subproblems
			  and their solutions because we do not know which
			  subproblem's solution will lead to the final answer
	- divide&conquer vs. dynamic programming
		- divide&conquer works when we can break the problem into
		    subproblems such that the subproblems do not overlap
		    too much
			- too much overlap can lead to an exponential number
			  of subproblems that must be solved
		- dynamic programming helps us deal with overlapping subproblemo			- often when subproblems overlap, each subproblem
			  will require the same computation, rather than
			  repeating the computation for each subproblem, do
			  the computation once and store the value in a table