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 | 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 |
Example:
RSA encryption.
|
|
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 |