Week 1: 
Reading: Notes
on Stable Marriages by Kevin Wayne 

Wednesday, January 4th 
Introduction. Stable
marriages.


Friday, January 6th 
Stable marriages continued.
Review of basics of Graph Theory. Notes


Week 2: 
Reading: Notes
on Hall's theorem and some applications by Allen Van
Gelder 

Wednesday, January 11th 
Matchings in bipartite
graphs. Hall's theorem. 

Friday, January
13th 
Edge
coloring bipartite graphs.


Week 3: 
Reading: Notes
on Matching markets by David Easley and Jon
Kleinberg 

Wednesday,
January 18th 
Vertex covers, Konig's
theorem


Friday, January
20th 
Matching
markets.

Assignment 1 assigned.

Week 4: 
Reading: For planar
graphs: Matousek and Nesetril, Chapter 5. For the art
gallery problem: Aigner and Ziegler, Chapter 26. 

Wednesday, January
25th 
Planar graphs: Euler's
Formula, platonic solids.


Friday, January
27th 
The 5color theorem; the
Art Gallery problem.

Assignment 1 due.

Week 5: 
Reading: Notes
on Fary's theorem by Will Evans. For Graph minors
and Kuratowksi's theorem see pages 35, 4043 of these
notes. 

Wednesday,
February 1st

Fary's theorem, Graph
Minors, Hadwiger's conjecture.


Friday, February
3rd

Kuratowski's theorem,
Menger's Theorem.

Assignment 2 assigned. 
Week 6: 


Wednesday, February
8th 
Discrete probability: quiz;
introduction.


Friday,
February 10th 
MIDTERM 

Week 7: 
Reading: Rosen, Sections 5.15.3


Wednesday, February 15th 
Conditional
probability: Bayes Theorem and applications; 
Assignment 2 due. 
Friday,
February 17th 
Independence. The Monty Hall
problem,Discrete random variables and expectation. 

Week 8: 
Reading: An article
on the secretary problem by Arnab Chakraborty. Notes
on hashing by Moses Charikar.


Wednesday, February 22nd 
The Secretary problem. The Birthday paradox. 

Friday,
February 24th 
Randomised Quicksort. Hashing: Balls and Bins. 
Assignment 3 assigned. 
Week 10: 
Notes
on Chernoff bounds by S. Chawla.


Wednesday, March 8th 
Chernoff bounds and applications

Assignment 3 due. 
Friday, March
10th











