| Date |
Topics covered |
Reference in Textbook
|
| Jan 05 |
Introduction, propositions, predicates, examples of theorems and proofs, types of proof techniques (slides) |
Kenneth Rosen Chapter 1 |
| Jan 10 |
Axioms, Mathematical Induction, Well-ordering principle, Strong Induction (slides) |
Kenneth Rosen Chapter 1, 4 |
| Jan 12 |
Sets, Russell's paradox, infinite sets, functions (slides) |
Kenneth Rosen Chapter 2++ |
| Jan 17 |
Countable and uncountable sets, Cantor's diagonalization technique (slides) |
Kenneth Rosen Chapter 2++ |
| Jan 19 |
Relations, Equivalence relations, partitions of a set (slides) |
Kenneth Rosen Chapter 7 |
| Jan 24 |
Tutorial |
Exercise Problem Sheets 1 and 2 |
| Jan 31 |
Relations: posets, chains, anti-chains (slides) |
Kenneth Rosen Chapter 7 |
| Feb 02 |
Basics of counting, double counting, binomial theorem, Pascal's triangle (slides) |
Kenneth Rosen Chapter 5 |
| Feb 06 |
Quiz 1 Also permutations, combinations with and without repetions, Estimating n! (slides) |
Kenneth Rosen Chapter 5 |
| Feb 09 |
Recurrence Relations and how to solve them (slides) |
Kenneth Rosen Chapter 6 |
| Feb 14 |
Solving recurrence relations via generating functions (slides) |
Kenneth Rosen Chapter 6 |
| Feb 16 |
Principle of Inclusion and Exclusion (slides) |
Kenneth Rosen Chapter 6 |
| Feb 21 |
Pigeon Hole Principle and its applications (slides) |
Kenneth Rosen Chapter 6 |
| Feb 23 |
Pigeon Hole Principle and its applications: A primer on Ramsey's theorem, Tutorial (slides) |
Kenneth Rosen Chapter 6++ |
| |
|
|
| Feb 28 |
Mid semester exam |
|
| |
|
|
| Mar 07 |
Graph theory: Basic terminology, Konigsberg's bridge problem, Eulerian graphs and a characterization (slides) |
Douglas West, Chapter 1 |
| Mar 09 |
Graph theory: Bipartite graphs and a characterization (slides) |
Douglas West, Chapter 1 |
| Mar 14 |
Graph theory: representing and comparing graphs, graph isomorphisms and automorphisms (slides) |
Douglas West, Chapter 1 |
| Mar 17 |
Graph theory: subgraphs, cliques and independent sets, large bipartite subgraphs, connected components and cut edges (slides) |
Douglas West, Chapter 1 |
| Mar 21 |
Graph theory: Matchings, perfect matchings, maximum matchings and a characterization via augumenting paths (slides) |
Douglas West, Chapter 3 |
| Mar 23 |
Graph theory: perfect matchings in bipartite graphs, Hall's theorem (slides) |
Douglas West, Chapter 3 |
| Mar 28 |
Tutorial on Graph theory |
Douglas West, Chapter 1, 3 |
| Apr 04 |
Quiz 2 |
|
| Apr 06 |
Graph theory: Stable matchings, Gale-Shapley theorem (slides) |
Douglas West, Chapter 3 |
| Apr 11 |
Abstract algebra: permutations and graph automorphisms, definition of abstract groups, examples (slides) |
Norman Biggs, Chapter 20 |
| Apr 13 |
Abstract algebra: More examples of groups, simple properties, subgroups, Abelian and cyclic groups (slides) |
Norman Biggs, Chapter 20 |
| Apr 18 |
Abstract algebra: Lagrange's theorem and its applications (slides) |
Norman Biggs, Chapter 20 |
| Apr 20 |
Abstract algebra: Applications to cryptography, Diffie-Hellman Key Exchange, RSA (slides) |
Norman Biggs, Chapter 20; Kenneth Rosen, Chapter 13 |