DISCRETE STRUCTURES I

Schedule.

Week 1.
  • Wednesday September 5th. Sets: Venn diagrams; set identities.
  • Friday September 7th. Logic: propositional calculus; logical operators.
    Reading: Notes on logic by Jacques Verstraete are posted here.

    Week 2.
  • Monday September 10th. Logic: logic rules; logic and sets.
  • Wednesday September 12th. Logic: conditional statements.
  • Friday September 14th. Logic: tautologies and contradictions. [Assignment 1 assigned.]

    Week 3.
  • Monday September 17th. Logic: combinatorial circuits; circuit complexity.
  • Wednesday September 19th. Example: P and NP.
  • Friday September 21st. Logic: logic and proofs.

    Week 4.
  • Monday September 24th. Example: Arrow's impossibility theorem.
    Reading: A paper on Arrow's result is posted here.
  • Wednesday September 26th. Logic: predicate calculus. [Assignment 1 due.]
  • Friday September 28th. Logic: proofs by induction. [Assignment 2 assigned.]

    Week 5.
  • Monday October 1st. Number Theory: prime factorisation.
  • Wednesday October 3rd. Number Theory: properties of the primes.
  • Friday October 5th. Number Theory: greatest common divisiors; Euclid's algorithm.

    Week 6.
  • Monday October 8th. Thanksgiving: No Lecture
  • Tuesday October 9th. Number Theory: modular arithmetic.
  • Wednesday October 10th. Number Theory: Fermat's little theorem. [Assignment 2 due.]
  • Friday October 12th. Number Theory: complexity issues. [Assignment 3 assigned.]

    Week 7.
  • Monday October 15th. Example: cryptography.
  • Wednesday October 17th. MIDTERM EXAM
  • Friday October 19th. Example: RSA encryption.

    Week 8.
  • Monday October 22nd. Combinatorics: functions; counting.
  • Wednesday October 24th. Combinatorics: subsets; the Binomial theorem. [Assignment 3 due.]
  • Friday October 26th. Combinatorics: Pascal's triangle. [Assignment 4 assigned.]

    Week 9.
  • Monday October 29th. Combinatorics: the Fibonacci numbers.
  • Wednesday October 31st. Combinatorics: solving recurrence equations.
  • Friday November 2nd. Combinatorics: inclusion-exclusion; the derangement problem.

    Week 10.
  • Monday November 5th. Combinatorics: inclusion-exclusion; Euler's function.
  • Wednesday November 7th. Combinatorics: the pigeon-hole principle. [Assignment 4 due.]
  • Friday November 9th. Combinatorics: the Multinomial theorem; the Shapley value. [Assignment 5 assigned.]

    Week 11.
  • Monday November 12th. Graph Theory: the Handshaking lemma.
  • Wednesday November 14th. Graph Theory: Euler circuits.
  • Friday November 16th. Graph Theory: Hamiltonian cycles.

    Week 12.
  • Monday November 19th. Graph Theory: trees.
  • Wednesday November 21st. Graph Theory: representing spanning trees. [Assignment 5 due.]
  • Friday November 23rd. Graph Theory: counting spanning trees. [Assignment 6 assigned. (Optional)]

    Week 13.
  • Monday November 26th. Graph Theory: planar graphs.
  • Wednesday November 28th. Graph Theory: graph colouring; characterising bipartite graphs.
  • Friday November 30th. Graph Theory: the 4-colour theorem; the 5-colour theorem.

    Week 14.
  • Monday December 3rd. Last Lecture: some game theory. Light reading: Notes on lizards.

    Week 15.
  • Monday December 10th. FINAL EXAM.