| Date |
Topics covered |
Reference in Textbook
|
| July 20 |
Introduction, propositions, predicates, examples of theorems and proofs. |
Kenneth Rosen Chapter 1 |
| July 21 |
Types of proof techniques. Mathematical induction, examples, well-ordering principle. |
Kenneth Rosen Chapter 1, Chapter 4 |
| July 23 |
Well-ordering principle, Strong Induction, Pop quiz. |
Kenneth Rosen Chapter 4 |
| July 27 |
Basic mathematical structures: sets, Russel's paradox, infinite sets, functions. |
Kenneth Rosen Chapter 2++ |
| July 28 |
Basic mathematical structures: sets, functions, comparing infinite sets using functions. |
Kenneth Rosen Chapter 2++ |
| July 30 |
Basic mathematical structures: countable and uncountable sets, Cantor's diagonalization argument. |
Kenneth Rosen Chapter 2++ |
| Aug 3 |
Basic mathematical structures: countable and uncountable sets, Continuum hypothesis. Relations. |
Kenneth Rosen Chapter 2++, Chapter 7 |
| Aug 4 |
Basic mathematical structures: relations, equivalence relations and partitions of a set, partial orders. |
Kenneth Rosen Chapter 7 |
| Aug 6 |
Basic mathematical structures: posets, chains, anti-chains, topological sort, applications to (parallel) task scheduling. |
Kenneth Rosen Chapter 7 |
| Aug 10 |
Basic mathematical structures: chains, anti-chains, lattices. |
Kenneth Rosen Chapter 7 |
| Aug 11 |
Basic mathematical structures: Lattices and their properties. |
Kenneth Rosen Chapter 7 |
| Aug 12 |
Quiz 1 |
|
| Aug 13 |
Counting techniques: product and sum principles, the bijection principle, double counting, Handshake lemma. |
Kenneth Rosen Chapter 5 |
| Aug 17 |
Counting techniques: the binomial theorem, Pascal's triangle, permutations and combinations with and without repetitions |
Kenneth Rosen Chapter 5 |
| Aug 18 |
Counting techniques: Estimating factorials, recurrence relations |
Kenneth Rosen Chapter 5, Chapter 6. |
| Aug 20 |
Counting techniques: Solving recurrence relations |
Kenneth Rosen Chapter 6 |
| Aug 24 |
Counting techniques: Solving recurrence relations via generating functions |
Kenneth Rosen Chapter 6 |
| Aug 25 |
Counting techniques: Applications of generating functions, Principle of Inclusion Exclusion and its applications |
Kenneth Rosen Chapter 6 |
| Aug 26 |
Counting techniques: Stirling numbers of the second kind and their properties |
Kenneth Rosen Chapter 6 |
| Aug 27 |
Counting techniques: Pigeon-hole principle (PHP), its variants and its applications |
Kenneth Rosen Chapter 5 |
| Aug 29 |
Quiz 2 |
|
| Aug 31 |
Counting techniques: Pigeon-hole principle, its variants and an extension of the coloring game |
Kenneth Rosen Chapter 5++ |
| Sept 01 |
Counting techniques: Extensions of PHP - an introduction to Ramsey theory |
Kenneth Rosen Chapter 5++ |
| Sept 03 |
Counting techniques: Bounds on Ramsey numbers, lower bound via the probabilistic method |
Kenneth Rosen Chapter 5++ |
| |
|
|
| Sept 09 |
Midsem |
|
| |
|
|
| Sept 14 |
Graph theory: Basic terminology, Konigsberg bridge problem, Eulerian graphs and a characterization |
Douglas West, Chapter 1 |
| Sept 15 |
Graph theory: Eulerian graphs, Bipartite graphs and a characterization |
Douglas West, Chapter 1 |
| Sept 21 |
Graph theory: Characterization of bipartite graphs, subgraphs; cliques and independent sets |
Douglas West, Chapter 1 |
| Sept 22 |
Graph theory: Large bipartite subgraphs of a graph; Graph isomorphism |
Douglas West, Chapter 1 |
| Sept 24 |
Graph theory: Graph automorphisms, connected components, cut edges |
Douglas West, Chapter 1 |
| Sept 28 |
Graph theory: Pop quiz |
Douglas West, Chapter 1 |
| Sept 29 |
Graph theory: connected components, cut edges, matchings |
Douglas West, Chapter 1, Chapter 3 |
| Oct 1 |
Graph theory: Matchings, Characterization of maximum matchings using augmenting paths |
Douglas West, Chapter 3 |
| Oct 5 |
Graph theory: Characterization of perfect matchings in bipartite graphs - Hall's theorem |
Douglas West, Chapter 3 |
| Oct 6 |
Graph theory: Applications of Hall's theorem, Vertex covers and their relation with matchings |
Douglas West, Chapter 3 |
| Oct 8 |
Graph theory: Minimum vertex covers and the Konig-Egervary theorem, stable matchings |
Douglas West, Chapter 3 |
| Oct 9 |
Quiz 3 |
|
| Oct 9 |
Graph theory: Stable matchings and the Gale Shapley algorithm |
Douglas West, Chapter 3 |
| Oct 12 |
Start of next topic: Abstract algebra and Number theory, permutations and graphs automorphisms, definition of an abstract group. |
Norman Biggs, Chapter 20 |
| Oct 13 |
Abstract algebra and Number theory: definition of an abstract group, more examples, some simple properties. |
Norman Biggs, Chapter 20 |
| Oct 15 |
Abstract algebra and Number theory: properties of a group, subgroups of a group. |
Norman Biggs, Chapter 20 |
| Oct 26 |
Abstract algebra and Number theory: cyclic groups, isomorphisms of a group. |
Norman Biggs, Chapter 20 |
| Oct 27 |
Abstract algebra and Number theory: properties of cyclic groups, order of subgroups of a group, Lagrange's theorem. |
Norman Biggs, Chapter 20 |
| Oct 29 |
Abstract algebra and Number theory: Proof and applications of Lagrange's theorem. |
Norman Biggs, Chapter 20 |
| Oct 31 |
Quiz 4 |
|
| Nov 2 |
Abstract algebra and Number theory: Modular arithmetic and applications to cryptography; the Diffie-Hellman protocol. |
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ |
| Nov 3 |
Abstract algebra and Number theory: Applications to cryptography, Euler-totient function, the RSA protocol. |
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ |