Date 
Topics covered 
Reference in Textbook

Jan 05 
Introduction, propositions, predicates, examples of theorems and proofs, types of proof techniques (slides) 
Kenneth Rosen Chapter 1 
Jan 10 
Axioms, Mathematical Induction, Wellordering principle, Strong Induction (slides) 
Kenneth Rosen Chapter 1, 4 
Jan 12 
Sets, Russell's paradox, infinite sets, functions (slides) 
Kenneth Rosen Chapter 2++ 
Jan 17 
Countable and uncountable sets, Cantor's diagonalization technique (slides) 
Kenneth Rosen Chapter 2++ 
Jan 19 
Relations, Equivalence relations, partitions of a set (slides) 
Kenneth Rosen Chapter 7 
Jan 24 
Tutorial 
Exercise Problem Sheets 1 and 2 
Jan 31 
Relations: posets, chains, antichains (slides) 
Kenneth Rosen Chapter 7 
Feb 02 
Basics of counting, double counting, binomial theorem, Pascal's triangle (slides) 
Kenneth Rosen Chapter 5 
Feb 06 
Quiz 1 Also permutations, combinations with and without repetions, Estimating n! (slides) 
Kenneth Rosen Chapter 5 
Feb 09 
Recurrence Relations and how to solve them (slides) 
Kenneth Rosen Chapter 6 
Feb 14 
Solving recurrence relations via generating functions (slides) 
Kenneth Rosen Chapter 6 
Feb 16 
Principle of Inclusion and Exclusion (slides) 
Kenneth Rosen Chapter 6 
Feb 21 
Pigeon Hole Principle and its applications (slides) 
Kenneth Rosen Chapter 6 
Feb 23 
Pigeon Hole Principle and its applications: A primer on Ramsey's theorem, Tutorial (slides) 
Kenneth Rosen Chapter 6++ 



Feb 28 
Mid semester exam 




Mar 07 
Graph theory: Basic terminology, Konigsberg's bridge problem, Eulerian graphs and a characterization (slides) 
Douglas West, Chapter 1 
Mar 09 
Graph theory: Bipartite graphs and a characterization (slides) 
Douglas West, Chapter 1 
Mar 14 
Graph theory: representing and comparing graphs, graph isomorphisms and automorphisms (slides) 
Douglas West, Chapter 1 
Mar 17 
Graph theory: subgraphs, cliques and independent sets, large bipartite subgraphs, connected components and cut edges (slides) 
Douglas West, Chapter 1 
Mar 21 
Graph theory: Matchings, perfect matchings, maximum matchings and a characterization via augumenting paths (slides) 
Douglas West, Chapter 3 
Mar 23 
Graph theory: perfect matchings in bipartite graphs, Hall's theorem (slides) 
Douglas West, Chapter 3 
Mar 28 
Tutorial on Graph theory 
Douglas West, Chapter 1, 3 
Apr 04 
Quiz 2 

Apr 06 
Graph theory: Stable matchings, GaleShapley theorem (slides) 
Douglas West, Chapter 3 
Apr 11 
Abstract algebra: permutations and graph automorphisms, definition of abstract groups, examples (slides) 
Norman Biggs, Chapter 20 
Apr 13 
Abstract algebra: More examples of groups, simple properties, subgroups, Abelian and cyclic groups (slides) 
Norman Biggs, Chapter 20 
Apr 18 
Abstract algebra: Lagrange's theorem and its applications (slides) 
Norman Biggs, Chapter 20 
Apr 20 
Abstract algebra: Applications to cryptography, DiffieHellman Key Exchange, RSA (slides) 
Norman Biggs, Chapter 20; Kenneth Rosen, Chapter 13 