Date 
Topics covered 
Reference in Textbook

July 20 
Introduction, propositions, predicates, examples of theorems and proofs. 
Kenneth Rosen Chapter 1 
July 21 
Types of proof techniques. Mathematical induction, examples, wellordering principle. 
Kenneth Rosen Chapter 1, Chapter 4 
July 23 
Wellordering principle, Strong Induction, Pop quiz. 
Kenneth Rosen Chapter 4 
July 27 
Basic mathematical structures: sets, Russel's paradox, infinite sets, functions. 
Kenneth Rosen Chapter 2++ 
July 28 
Basic mathematical structures: sets, functions, comparing infinite sets using functions. 
Kenneth Rosen Chapter 2++ 
July 30 
Basic mathematical structures: countable and uncountable sets, Cantor's diagonalization argument. 
Kenneth Rosen Chapter 2++ 
Aug 3 
Basic mathematical structures: countable and uncountable sets, Continuum hypothesis. Relations. 
Kenneth Rosen Chapter 2++, Chapter 7 
Aug 4 
Basic mathematical structures: relations, equivalence relations and partitions of a set, partial orders. 
Kenneth Rosen Chapter 7 
Aug 6 
Basic mathematical structures: posets, chains, antichains, topological sort, applications to (parallel) task scheduling. 
Kenneth Rosen Chapter 7 
Aug 10 
Basic mathematical structures: chains, antichains, lattices. 
Kenneth Rosen Chapter 7 
Aug 11 
Basic mathematical structures: Lattices and their properties. 
Kenneth Rosen Chapter 7 
Aug 12 
Quiz 1 

Aug 13 
Counting techniques: product and sum principles, the bijection principle, double counting, Handshake lemma. 
Kenneth Rosen Chapter 5 
Aug 17 
Counting techniques: the binomial theorem, Pascal's triangle, permutations and combinations with and without repetitions 
Kenneth Rosen Chapter 5 
Aug 18 
Counting techniques: Estimating factorials, recurrence relations 
Kenneth Rosen Chapter 5, Chapter 6. 
Aug 20 
Counting techniques: Solving recurrence relations 
Kenneth Rosen Chapter 6 
Aug 24 
Counting techniques: Solving recurrence relations via generating functions 
Kenneth Rosen Chapter 6 
Aug 25 
Counting techniques: Applications of generating functions, Principle of Inclusion Exclusion and its applications 
Kenneth Rosen Chapter 6 
Aug 26 
Counting techniques: Stirling numbers of the second kind and their properties 
Kenneth Rosen Chapter 6 
Aug 27 
Counting techniques: Pigeonhole principle (PHP), its variants and its applications 
Kenneth Rosen Chapter 5 
Aug 29 
Quiz 2 

Aug 31 
Counting techniques: Pigeonhole principle, its variants and an extension of the coloring game 
Kenneth Rosen Chapter 5++ 
Sept 01 
Counting techniques: Extensions of PHP  an introduction to Ramsey theory 
Kenneth Rosen Chapter 5++ 
Sept 03 
Counting techniques: Bounds on Ramsey numbers, lower bound via the probabilistic method 
Kenneth Rosen Chapter 5++ 



Sept 09 
Midsem 




Sept 14 
Graph theory: Basic terminology, Konigsberg bridge problem, Eulerian graphs and a characterization 
Douglas West, Chapter 1 
Sept 15 
Graph theory: Eulerian graphs, Bipartite graphs and a characterization 
Douglas West, Chapter 1 
Sept 21 
Graph theory: Characterization of bipartite graphs, subgraphs; cliques and independent sets 
Douglas West, Chapter 1 
Sept 22 
Graph theory: Large bipartite subgraphs of a graph; Graph isomorphism 
Douglas West, Chapter 1 
Sept 24 
Graph theory: Graph automorphisms, connected components, cut edges 
Douglas West, Chapter 1 
Sept 28 
Graph theory: Pop quiz 
Douglas West, Chapter 1 
Sept 29 
Graph theory: connected components, cut edges, matchings 
Douglas West, Chapter 1, Chapter 3 
Oct 1 
Graph theory: Matchings, Characterization of maximum matchings using augmenting paths 
Douglas West, Chapter 3 
Oct 5 
Graph theory: Characterization of perfect matchings in bipartite graphs  Hall's theorem 
Douglas West, Chapter 3 
Oct 6 
Graph theory: Applications of Hall's theorem, Vertex covers and their relation with matchings 
Douglas West, Chapter 3 
Oct 8 
Graph theory: Minimum vertex covers and the KonigEgervary theorem, stable matchings 
Douglas West, Chapter 3 
Oct 9 
Quiz 3 

Oct 9 
Graph theory: Stable matchings and the Gale Shapley algorithm 
Douglas West, Chapter 3 
Oct 12 
Start of next topic: Abstract algebra and Number theory, permutations and graphs automorphisms, definition of an abstract group. 
Norman Biggs, Chapter 20 
Oct 13 
Abstract algebra and Number theory: definition of an abstract group, more examples, some simple properties. 
Norman Biggs, Chapter 20 
Oct 15 
Abstract algebra and Number theory: properties of a group, subgroups of a group. 
Norman Biggs, Chapter 20 
Oct 26 
Abstract algebra and Number theory: cyclic groups, isomorphisms of a group. 
Norman Biggs, Chapter 20 
Oct 27 
Abstract algebra and Number theory: properties of cyclic groups, order of subgroups of a group, Lagrange's theorem. 
Norman Biggs, Chapter 20 
Oct 29 
Abstract algebra and Number theory: Proof and applications of Lagrange's theorem. 
Norman Biggs, Chapter 20 
Oct 31 
Quiz 4 

Nov 2 
Abstract algebra and Number theory: Modular arithmetic and applications to cryptography; the DiffieHellman protocol. 
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ 
Nov 3 
Abstract algebra and Number theory: Applications to cryptography, Eulertotient function, the RSA protocol. 
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ 