DISCRETE STRUCTURES II

Schedule.

Week 1.
  • Tuesday January 10th. Stable Marriages.
  • Thursday January 12th. Matchings; Augmenting Paths; Hall's Theorem.
  • Friday January 13th. Tutorial: Review of basic graph concepts. (McConnell Room 103, 4pm-6pm)

    Week 2.
  • Tuesday January 17th. Applications of Hall's theorem: Latin Squares; Regular graphs; Systems of Distinct Representatives.
  • Thursday January 19th. Konig-Egervary Theorem, Vertex Cover and applications. [Assignment 1 assigned.]
    Week 3.
  • Tuesday January 24th. Edge colouring: scheduling; Clos networks.
  • Thursday January 26th. Matching Markets.
    Week 4.
  • Tuesday January 31st. Planar graphs: Euler's Formula; the Platonic solids. [Assignment 1 due.]
  • Thursday February 2nd. The 5-colour theorem; the Art Gallery theorem. [Assignment 2 assigned.]
    Week 5.
  • Tuesday February 7th. Graph Connectivity: Menger's Theorem.
  • Thursday February 9th. Graph Minors; Kuratowski's theorem.
    Week 6.
  • Tuesday February 14th. Planar graphs: Fary's theorem; Planar Duality. [Assignment 2 due.]
  • Thursday February 16th. Midterm Exam.

    Week 7.
    Spring Break - No Lectures.

    Week 8.
  • Tuesday February 28th. Discrete probability: quiz and introduction.
  • Thursday March 1st. Conditional probability: Bayes Theorem and applications; Independence. [Assignment 3 assigned.]
    Week 9.
  • Tuesday March 6th. The Monty Hall problem; Discrete random variables and expectations.
  • Thursday March 8th. The Secretary problem; the Birthday problem.
    Week 10.
  • Tuesday March 13th. Randomised Quicksort.; Hashing; Balls and Bins.
  • Thursday March 15th. Random Walks; web search engines. The Chernoff Bound. [Assignment 3 due.] [Assignment 4 assigned.]
    Week 11.
  • Tuesday March 20th. Applications of the Chernoff Bound: Balls and Bins; Statistical Trials; Quicksort.
  • Thursday March 22nd. Independent mortgages: the housing crash.
  • Friday March 23rd. Tutorial: Review of basic combinatorics. (McConnell Room 320, 4pm-6pm)

    Week 12.
  • Tuesday March 27th. Bijections: labelled spanning trees; the Catalan numbers.
  • Thursday March 29th. The Generating Function Method: the Tower of Hanoi; the Fibonnaci numbers. [Assignment 4 due.] [Assignment 5 assigned.]
    Week 13.
  • Tuesday April 3rd. Compositions and Convolutions: fruit, money.
  • Thursday April 5th. Operations on Ordinary Generating Functions: Sum of Squares; the Catalan Numbers. [Assignment 6 posted (Optional).]
    Week 14.
  • Tuesday April 10th. Operations on Exponential Generating Functions: Derangements; the Bell Numbers.
  • Thursday April 12th. Guest Lecture: De Bruijn Sequences (Aaron Williams). [Assignment 5 due.]
    Week 15.
  • Thursday April 19th. Tutorial: Review Session. (McConnell Room 103, 4pm-6pm)


    Week 16.
  • Monday April 23. Final Exam.