Lectures, Handouts, and Readings
(For reading pdf files, you need Adobe
Acrobat, and for reading postscript files, you need ghostview)
March 26, 2003
Administrivia; The Snafooz puzzle; Polygons, their representations;
Rectilinear polygons
April 2, 2003
Geometric structures; Voronoi diagram and Delaunay
triangulation; Planarity; Application of planar graphs to routing in ad
hoc wireless networks
April 9, 2003
Algorithm design techniques: Solving the maximum
sum subarray problem
-
Column 8 of Programming
Pearls, by Jon Bentley, discusses the maxsum subarray problem we covered
in class
-
Notes
covering the different algorithms discussed in the above column.
In class, we covered only 1 algorithm (a variant of the final one given
in the notes) since we developed the best algorithm very quickly!
April 16, 2003
Content delivery networks
-
A presentation on Akamai's content delivery network,
by Ravi Sundaram
-
Homework
3
April 23, 2003
The Stable Marriage problem; the Traditional Marriage
algorithm, proof of termination and stability
April 30, 2003
Problems from the ACM International Programming
Contest; the Longest Decreasing Subsequence problem; Dynamic programming
and greedy algorithms; making change
May 7, 2003
More problems from the ACM International Programming
Contest; 5 problems were assigned. One problem discussed
ICPC 2003 problems available on their archives
Quiz
2
Homework
5
May 14, 2003
Introduction to complexity theory and NP-completeness;
P vs NP; Satisfiability, TSP, Factoring, and Clique problems; Reductions
May 21, 2003
Introduction to quantum computing; the experiment
with polarizing lenses; the quantum key exchange protocol
Introduction
to quantum computing for non-physicists