MATH 240 - DISCRETE STRUCTURES I.  Fall 2011


Tentative schedule


Week 1:

Friday, September 2nd Introduction. Sets: Venn diagrams; set identities.

Wednesday, September 7th Logic: propositional calculus; logical operators.
Friday, September 9th
Logic: The conditional and biconditional (equivalence) statements.

Week 2
:

Reading: Notes on logic by Jacques Verstraete are posted here. Also compare with Rosen.

Monday, September 12th Logic: tautologies and contradictions. Examples of Direct Proofs and Proof by Contradiction. Assignment 1 assigned.
Wednesday, September 14th Logic: combinatorial circuits; circuit complexity.
Friday, September 16th 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).

Week 3
:


Monday, September 19th Example: P and NP.
Wednesday, September 21st Arrow's impossibility theorem. See these notes.

Friday, September 23rd Logic: predicate calculus.
Assignment 1 due.

Week 4
:


Monday, September 26th Logic: proofs by induction.
Wednesday, September 28th
Number Theory: prime factorisation.
Friday, September 30th Number Theory: applications of unique prime factorizations.


Week 5:


Monday, October 3rd Number Theory: Greatest common divisiors.
Assignment 2 assigned.
Wednesday, October 5th Number Theory: Euclid's Algorithm.
Friday, October 7th Number Theory: Modular arithmetic.

Week 6
:


Monday, October 10th Thansgiving. No lecture.

Wednesday, October 12th Number Theory: Modular arithmetic and prime fields.
Assignment 2 due.
Friday, October 14th
Midterm. See practice Midterm here with solutions.
Assignment 3 assigned.

Week 7
:


Monday, October 17th Number Theory: Modular Equations. 
Wednesday, October 19th Number Theory: Fermat Test, Miller-Rabin Test, Recognizing Primes.

Friday, October 21st Example: cryptography.

Week 8:


Monday, October 24th
Wednesday, October 26th Combinatorics: functions, counting.
Friday, October 28th Combinatorics: subsets; the Binomial theorem.

Week 9:


Monday, October 31st Combinatorics: Pascal's triangle. Assignment 3 due, assignment 4 assigned.
Wednesday, Nov 2nd
Combinatorics: solving recurrence equations.
Friday, November 4th Combinatorics: inclusion-exclusion.

Week 10
:


Monday, November 7th Combinatorics: inclusion-exclusion; the derangement problem.
Wednesday, November 9th Combinatorics: inclusion-exclusion; Euler's function.
Friday November 11th. Combinatorics: the Multinomial theorem.

Week 11
:


Monday, November 14th Graph Theory: the Handshaking lemma. Euler circuits. Assignment 4 due, assignment 5 assigned.
Wednesday, November 16th Graph Theory: Hamiltonian cycles.
Friday, November 18th. Graph Theory: trees.

Week 12
:


Monday, November 21st Graph Theory: representing spanning trees.
Wednesday, November 23rd Graph Theory: counting spanning trees.
Friday, November 25th Graph Theory: planar graphs.

Week 13
:


Monday November 28th Graph Theory: graph coloring; characterising bipartite graphs. Assignment 5 due.
Wednesday, November 30th
Graph Theory: the 4-color theorem; the 5-color theorem.
Friday, December 2nd Game Theory

Week 14:

Monday, December 5th
Review


Thursday, December 22nd

FINAL EXAM