DISCRETE STRUCTURES I

Schedule.

Week 1.
  • Wednesday September 1st. Sets: Venn diagrams; set identities.
  • Friday September 3rd. Logic: propositional calculus; logical operators.
    Reading: Notes on logic by Jacques Verstraete are posted here. Also compare with Rosen.

    Week 2.
  • Wednesday September 8th. Logic: The conditional and biconditional (equivalence) statements.
  • Friday September 10th. Logic: tautologies and contradictions. Examples of Direct Proofs and Proof by Contradiction.

    Week 3.
  • Monday September 13th. Logic: combinatorial circuits; circuit complexity. [Assignment 1 assigned.]
  • Wednesday September 15th. Asymptotic Bounds. Polynomial and Exponential Time Algorithms. For more background on the topic of this and the next lecture see these notes (especially Section 5). Here are some sample questions on order notation for practice (I'll provide some solutions at a later date).
  • Friday September 17th. Example: P and NP.

    The Midterm will take place on Monday October 25. In 2 classrooms. I will let you know later who writes where!

    Week 4.
  • Monday September 20th. Predicate Calculus
  • Wednesday September 22th. Logic: predicate calculus.
  • Friday September 24th. Logic: proofs by induction. [Assignment 1 due.]

    Week 5.
  • Monday September 27. finished off proof by counter example and strong induction. Number Theory: prime factorisation.
  • Wednesday September 29. Number Theory: applications of unique prime factorizations. algorithms (is $N$ a prime? find a prime factorization).[Assignment 2 assigned.]
  • Friday October 1st. Number Theory: greatest common divisiors; Euclid's algorithm.

    Week 6.
  • Monday October 4th. Number Theory: Runtime of Euclid's Algorithm.
  • Wednesday October 6th. Number Theory: Input sizes, and polytime algorithms. Modular arithmetic.
  • Friday October 8th. Number Theory: Modular arithmetic and prime fields.

    Week 7.
  • Monday October 11th. Thanksgiving. No lecture.
  • Wednesday October 13th. Number Theory: Modular Equations [Assignment 2 due.]
  • Friday October 15th. Number Theory: Fermat Test, Miller-Rabin Test, Recognizing Primes.

    Week 8.
  • Monday October 18th. Example: cryptography.
  • Wednesday October 20th. Example: RSA encryption.
  • Friday October 20th. Combinatorics: functions; counting.

    Week 9.
  • Monday October 25th. Midterm.
  • Wednesday October 27th. Combinatorics: subsets; the Binomial theorem.
  • Friday October 29th Combinatorics: Pascal's triangle. [Assignment 4 assigned.]

    Week 10.
  • Monday Nov 1. Combinatorics: solving recurrence equations. [Assignment 3 due.]
  • Wednesday Nov 3. Combinatorics: inclusion-exclusion.
  • Friday November 5th. Combinatorics: inclusion-exclusion; the derangement problem.



    Week 11.
  • Monday November 8th. Combinatorics: inclusion-exclusion; Euler's function.
  • Wednesday November 10th. Combinatorics: the pigeon-hole principle.
  • Friday November 12th. Combinatorics: the Multinomial theorem.

    The following is not updated and tentative:

    Week 12.
  • Monday November 15th. Graph Theory: the Handshaking lemma. Euler circuits.[Assignment 4 due.] [Assignment 5 assigned]
  • Wednesday November 17th. Graph Theory: Hamiltonian cycles.
  • Friday November 19th. Graph Theory: trees.

    Week 13.
  • Monday November 22nd. Graph Theory: representing spanning trees.
  • Wednesday November 24th. Graph Theory: counting spanning trees.
  • Friday November 26th. Graph Theory: planar graphs.

    Week 14.
  • Monday November 29th. Graph Theory: graph colouring; characterising bipartite graphs.[Assignment 5 due.]
  • Wednesday Dec 1. Graph Theory: the 4-colour theorem; the 5-colour theorem.
  • Friday Dec 3. Approximation Algorithms, Colourings and Multiflows



    Week 15.
  • Tuesday December 7th. FINAL EXAM.