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