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