MATH 340 - DISCRETE STRUCTURES II.  Winter 2017


Schedule (UNDER CONSTRUCTION)


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