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 5-color 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, 40-43 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.1-5.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
|
|
|
|
|
|
|
|
|
|
|
|