| Date |
Topics covered |
Reference in Textbook
|
| July 21 |
Introduction, propositions, predicates, examples of theorems and proofs, types of proofs. (slides) |
Kenneth Rosen Chapter 1 |
| July 22 |
Proof techniques: Mathematical induction, examples, well-ordering principle, strong induction. (slides) |
Kenneth Rosen Chapter 4 |
| July 24 |
Pop Quiz on induction. Basic mathematical structures: finite and infinite sets, functions, Russell's paradox, the Hilbert's hotel example. (slides) |
Kenneth Rosen Chapter 2 |
| July 28 |
Special lecture by Khushraj Madnani: Propositional logic, predicates and quantifiers, rules of inference.
|
Kenneth Rosen Chapter 1 |
| July 31 |
Basic mathematical structures: types of functions, properties of finite and infinite sets through functions, countable sets and their properties. (slides)
|
Kenneth Rosen Chapter 2 |
| Aug 04 |
Countable and uncountable sets, Cantor's diagonalization technique, Cantor's paradox, Continuum Hypothesis; Relations. (slides)
|
Kenneth Rosen Chapter 2 |
| Aug 05 |
Representation and types of relations, equivalence relations and partitions, more examples. (slides)
|
Kenneth Rosen Chapter 7 |
| Aug 07 |
Partial order relations: posets, chains, anti-chains, topological sorting, Mirsky's theorem, application to parallel task scheduling. (slides)
|
Kenneth Rosen Chapter 7 |
| Aug 11 |
Recap of partial order relations, Mirsky's theorem, Statement of Dilworth's theorem. Introduction to counting and combinatorics, simple examples, some basic principles of counting. (slides)
|
Kenneth Rosen Chapter 7, Chapter 5 |
| Aug 12 |
Basic counting techniques: sum and product principles, permutations and combinations, counting number of (ordered) subsets, double counting, Handshake lemma (slides)
|
Kenneth Rosen Chapter 5 |
| Aug 13 |
Quiz 1
|
|
| Aug 18 |
Basic counting techniques: double counting and bijective principles, Cayley's theorem of labeled trees, binomial theorem (slides)
|
Kenneth Rosen Chapter 5++ |
| Aug 19 |
Binomial theorem, Fun with Pascal's triangle, permutation and combinations with repetitions, estimating n! (slides)
|
Kenneth Rosen Chapter 5 |
| Aug 21 |
Recurrence relations, Fibonacci sequence, Catalan numbers, solving linear recurrences (slides)
|
Kenneth Rosen Chapter 6 |
| Aug 25 |
Solving the Fibonacci recurrence and other linear recurrences, power series and generating functions(slides)
|
Kenneth Rosen Chapter 6 |
| Aug 26 |
Generating functions: examples, properties, and applications. Solving the Catalan recurrence, counting, proving binomial identities (slides)
|
Kenneth Rosen Chapter 6 |
| Aug 28 |
Principle of Inclusion and Exclusion and its applications: number of surjections, number of derangements (slides)
|
Kenneth Rosen Chapter 6 |
| Sept 01 |
Quiz 2
|
|
| Sept 01 |
Pigeon-Hole Principle and its applications (slides)
|
Kenneth Rosen Chapter 5 |
| Sept 02 |
Variants of Pigeon-Hole Principle, extensions of the coloring game, introduction to Ramsey theory (slides)
|
Kenneth Rosen Chapter 5++ |
| Sept 04 |
Introduction to Ramsey theory: proof of Ramsey's theorem for 2 colors, some more examples, Ramsey numbers. (slides)
|
++ |
| | | |
| Sept 10 |
Midsem
|
|
| | | |
| Sept 15 |
Bounds on Ramsey numbers, lower bound using the probabilistic method. Start of next topic: Graph theory, what are graphs, Konigsberg Bridge problem (slides)
|
++ |
| Sept 16 |
Introduction to Graph theory: basic terminology, Eulerian graphs and their characterization using degrees of vertices (slides)
|
Douglas West, Chapter 1, Section 1.1, 1.2 |
| Sept 18 |
Eulerian graphs, bipartite graphs and their characterization using odd cycles (slides)
|
Douglas West, Chapter 1, Sections 1.1, 1.2 |
| Sept 22 |
Bipartite graphs, subgraphs, cliques and independent sets, degree sum formula (slides)
|
Douglas West, Chapter 1, Sections 1.1-1.3 |
| Sept 23 |
Finding large bipartite subgraphs, graph representations and isomorphism, some special graphs (slides)
|
Douglas West, Chapter 1, Sections 1.1-1.3 |
| Sept 24 |
Graph isomorphism, Graph automorphism, connected components of a graph (slides)
|
Douglas West, Chapter 1, Sections 1.1-1.3 |
| Sept 25 |
Connected components, cut-edges, matchings (slides)
|
Douglas West, Chapter 1, Chapter 3 |
| Sept 29 |
Perfect, maximal and maximum matchings, symmetric difference, characterization of maximum matchings using augmenting paths (slides)
|
Douglas West, Chapter 3, Section 3.1 |
| Sept 30 |
Characterizing perfect matchings in bipartite graph: Hall's condition (slides)
|
Douglas West, Chapter 3, Section 3.1 |
| Oct 07 |
Quiz 3
|
|
| Oct 07 |
Hall's theorem, matchings and vertex covers (slides)
|
Douglas West, Chapter 3, Section 3.1 |
| Oct 09 |
Matchings and vertex covers: Konig-Egervary theorem and applications (slides)
|
Douglas West, Chapter 3, Section 3.1 |
| Oct 13 |
Stable matchings and the Gale Shapley algorithm (slides)
|
Douglas West, Chapter 3, Section 3.2 |
| Oct 14 |
Start of next topic: Abstract algebra and Number theory, permutations and graph automorphisms, definition of a group (slides)
|
Norman Biggs, Chapter 20 |
| Oct 16 |
Abstract algebra -- groups: definitions, examples and simple properties (slides)
|
Norman Biggs, Chapter 20 |
| Oct 27 |
Abstract algebra -- symmetries of an equilateral triangle, Abelian groups, subgroups (slides)
|
Norman Biggs, Chapter 20 |
| Oct 28 |
Abstract algebra -- order of a group, cyclic groups, group isomorphisms (slides)
|
Norman Biggs, Chapter 20 |
| Oct 30 |
Abstract algebra -- Lagrange's theorem (slides)
|
Norman Biggs, Chapter 20 |
| Nov 01 |
Abstract algebra -- Some corollaries and applications of Lagrange's theorem (slides)
|
Norman Biggs, Chapter 20 |
| Nov 03 |
Quiz 4
|
|
| Nov 03 |
Number theory and applications to cryptography -- Modular arithmetic, Diffie-Hellman Key exchange protocol (slides)
|
Kenneth Rosen Chapter 3, ++ |
| Nov 05 |
Number theory and applications to cryptography -- Some more modular arithmetic, Euler totient function, the RSA cryptosystem (slides)
|
Kenneth Rosen Chapter 3 |