DISCRETE STRUCTURES II

Tentative Lecture Schedule.

Week 1.
  • Tuesday January 8th. Stable Marriages.
  • Thursday January 10th. Matchings; Augmenting Paths; Hall's Theorem.
  • Friday January 11th. (Confirmed) Tutorial: Review of basic graph concepts. (Burnside Hall Room 1205: 3:30-5:30PM)

    Week 2.
  • Tuesday January 15th. Applications of Hall's theorem: Latin Squares; Regular graphs; Systems of Distinct Representatives.
  • Thursday January 17th. Konig-Egervary Theorem, Vertex Cover and applications. [Assignment 1 assigned.]
    Week 3.
  • Tuesday January 22nd. Edge colouring: scheduling; Clos networks.
  • Thursday January 24th. Matching Markets.
    Week 4.
  • Tuesday January 29th. Planar graphs: Euler's Formula.
  • Thursday January 31st. Basics of convex polytopes; Platonic Solids; the Art Gallery theorem.

    [Assignment 1 due on MyCourses 7PM.] [Assignment 2 assigned on Friday Feb. 1.]
    Week 5.
  • Tuesday February 5th. Pick's Theorem (lattice points and areas); Planar duality; 4, 5 and 6-Colour Theorems.
  • Thursday February 7th. Graph Connectivity (Definitions only): Graph Minors; Kuratowski's theorem.
  • Friday February 8th. (Confirmed) Review/ Q+A Session. (Burside Hall Room 1205: 3:30-5:00PM)

    Week 6.
  • Tuesday February 12th. Planar graphs: Fary's theorem; intersection and contact graphs; Thurston's Theorem; interval graphs.
  • Wednesday February 13th. [Assignment 2 due on MyCourses.]

  • Thursday February 14th. Midterm Exam.

    Week 7.
  • Tuesday February 19th. Menger's Theorem.
  • Thursday February 21. Flows on the Internet. Week 8.
  • Tuesday February 26th. Discrete probability: quiz and introduction.
  • Tuesday February 28th. Conditional probability: Bayes Theorem and applications; Independence. [Assignment 3 assigned.]
    Week 9.
    Spring Break - No Lectures.

    Week 10.
  • Tuesday March 12th. The Monty Hall problem; Discrete random variables and expectations.
  • Thursday March 14th. The Secretary problem; the Birthday problem.

    Week 10.
  • Tuesday March 19th. Randomised Quicksort.; Hashing; Balls and Bins.
  • Thursday March 21st. Random Walks; web search engines. The Chernoff Bound. [Assignment 3 due.] [Assignment 4 assigned.]
    Week 11.
  • Tuesday March 26th. Applications of the Chernoff Bound: Balls and Bins; Statistical Trials; Quicksort.
  • Thursday March 28th. Independent mortgages: the housing crash.
  • Friday March 23rd. Tutorial: Review of basic combinatorics. (Burnside Hall Room 1205, 330-530 PM)

    Week 12.
  • Tuesday April 2nd. Bijections: labelled spanning trees; the Catalan numbers.
  • Thursday April 4th. The Generating Function Method: the Tower of Hanoi; the Fibonnaci numbers. [Assignment 4 due.] [Assignment 5 assigned.]
    Week 13.
  • Tuesday April 9th. Compositions and Convolutions: fruit, money.
  • Thursday April 11th. Operations on Ordinary Generating Functions: Sum of Squares; the Catalan Numbers. [Assignment 6 posted - (Exercise sheet. not for marks).][Assignment 5 due.]
    Week 15.
  • No activities April 15-19.

    Week 16
  • Question and Answer Session. Monday, April 22nd. TBA.
  • Final Exam. Tuesday, April 23rd. 6-9PM.