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 ++ |