I'll be posting the lecture notes and assignment solutions here.
News: My office hour on February 3rd and 10th is cancelled,
as I'm away for a workshop.
Jan 17th, 2006:
We discussed the weaker version of master theorem, namely divide
and conquer relations, and a technique to solve recurrence relations with
full history. The lecture notes are here.
[ps][pdf]
March 14th, 2006:
Introduction on Dynamic Programming: we looked at a couple of simple
examples on DP algorithms(fibonacci sequence, binomial coefficient,..)
and studied the coin change problem. Again, any attempts on the
two exercises problems are welcome. The lecture notes are here.
[ps][pdf]
March 16th, 2006:
All-pairs shortest path problem. Matrix Multiplications using DP.
The lecture notes are here.
[ps][pdf]
Jan 27th, 2006:
Assignment #1 Solution
[ps][pdf]
Mar 20th, 2006:
Assignment #3 Solution
[ps][pdf]
Mar 22th, 2006:
Assignment #3 Solution(Supplement):
Model solutions are available. Note that these are demo solutions
only. Many thanks to Dorna Kashef and James McKinney, who kindly
allowed us to make their solutions available to the class.
[Dorna's Speller]
[James's Speller]
[James's LineSegmentIntersection]