| Date |
Topics covered |
Reference in Textbook
|
| August 07 |
Introduction, propositions, predicates, examples of theorems and proofs. (slides) |
Kenneth Rosen Chapter 1 |
| August 08 |
Types of proof techniques. Axioms. Mathematical induction, examples. (slides) |
Kenneth Rosen Chapter 1, Chapter 4 |
| August 10 |
Induction and the Well-ordering principle. (slides) |
Kenneth Rosen Chapter 4 |
| August 14 |
Strong Induction and more examples. (slides) |
Kenneth Rosen Chapter 4 |
| |
|
|
| August 17 |
Basic mathematical structures: sets, examples, Russell's paradox. (slides) |
Kenneth Rosen Chapter 2++ |
| August 21 |
Basic mathematical structures: functions, comparing infinite sets using functions. (slides) |
Kenneth Rosen Chapter 2++ |
| August 22 |
Pop quiz, Basic mathematical structures: countable and countably infinite sets. (slides) |
Kenneth Rosen Chapter 2++ |
| August 24 |
Basic mathematical structures: countable and uncountable sets (slides) |
Kenneth Rosen Chapter 2++ |
| August 28 |
Basic mathematical structures: uncountable sets, relations, partitions of a set. (slides) |
Kenneth Rosen Chapter 7 |
| August 29 |
Basic mathematical structures: equivalence relations, equivalence classes and partitions of a set. (slides) |
Kenneth Rosen Chapter 7 |
| August 31 |
Basic mathematical structures: partial order relations, posets. (slides) |
Kenneth Rosen Chapter 7 |
| Sept 01 |
Quiz 1 |
|
| Sept 04 |
Basic mathematical structures: posets, chains, anti-chains, topological sort. (slides) |
Kenneth Rosen Chapter 7 |
Sept 05 |
Basic mathematical structures: chains, anti-chains, parallel-task scheduling, Mirsky's theorem. (slides) |
Kenneth Rosen Chapter 7 |
Sept 07 |
Basic mathematical structures: minimal/maximal vs minimum/maximum elements, glb/lub, lattices. (slides) |
Kenneth Rosen Chapter 7 |
| |
|
|
| Sept 11 |
Counting techniques: product and sum principles, the bijection principle, double counting, Handshake lemma. (slides) |
Kenneth Rosen Chapter 5 |
| Sept 12 |
Counting techniques: the binomial theorem, Pascal's triangle, permutations and combinations with and without repetitions. (slides) |
Kenneth Rosen Chapter 5 |
| Sept 14 |
Estimating factorials, Recurrence relations, Fibonacci Sequence (slides) |
Kenneth Rosen Chapter 5 |
| Sept 23 |
Midsem |
|
| Sept 25 |
Counting techniques: recurrence relations and how to solve them (slides) |
Kenneth Rosen Chapter 6 |
| Sept 26 |
Counting techniques: Solving recurrence relations via generating functions (slides) |
Kenneth Rosen Chapter 6 |
| Oct 03 |
Counting techniques: Applications of generating functions, Principle of Inclusion Exclusion and its applications (slides) |
Kenneth Rosen Chapter 6 |
| Oct 05 |
Counting techniques: Pigeon-hole principle (PHP), its variants and its applications (slides) |
Kenneth Rosen Chapter 5 |
| Oct 09 |
Applications and Extensions of PHP to the coloring game (slides) |
Kenneth Rosen Chapter 5++ |
| Oct 10 |
Extensions of PHP - a glimpse of Ramsey theory (slides) |
Kenneth Rosen Chapter 5++ |
| |
|
|
| Oct 12 |
Graph theory: Basic terminology, Konigsberg bridge problem, Eulerian graphs (slides) |
Douglas West, Chapter 1 |
| Oct 16 |
Graph theory: Eulerian graphs and a characterization (slides) |
Douglas West, Chapter 1 |
| Oct 17 |
Graph theory: Application of Eulerian Graphs, Bipartite graphs (slides) |
Douglas West, Chapter 1 |
| Oct 19 |
Graph theory: Characterization of Bipartite graphs, Graph isomorphism (slides) |
Douglas West, Chapter 1 |
| Oct 23 |
Graph theory: Representation of graphs, Graph isomorphisms, automorphisms. Subgraphs, cliques and independent sets (slides) |
Douglas West, Chapter 1 |
| Oct 26 |
Graph theory: cliques and independent sets, connected components, cut edges (slides) |
Douglas West, Chapter 1 |
| Oct 27 |
Quiz 2 |
|
| Oct 30 |
Graph theory: Matchings, Perfect and maximum matchings (slides) |
Douglas West, Chapter 3 |
| Oct 31 |
Graph theory: Characterization of maximum matchings using Augmenting paths (slides) |
Douglas West, Chapter 3 |
| Nov 02 |
Graph theory: Characterization of perfect matchings in bipartite graphs - Hall's theorem and some applications (slides) |
Douglas West, Chapter 3 |
| Nov 06 |
Graph theory: Minimum vertex covers and the Konig-Egervary theorem (slides) |
Douglas West, Chapter 3 |
| Nov 07 |
Graph theory: Stable matchings and the Gale Shapley algorithm (slides) |
Douglas West, Chapter 3 |
| Nov 09 |
Graph theory: Gale Shapley algorithm and its optimality (slides) |
Douglas West, Chapter 3 |