Date 
Topics covered 
Reference in Textbook

July 21 
Introduction, propositions, predicates, examples of theorems and proofs, types of proofs. (slides) 
Kenneth Rosen Chapter 1 
July 22 
Proof techniques: Mathematical induction, examples, wellordering principle, strong induction. (slides) 
Kenneth Rosen Chapter 4 
July 24 
Pop Quiz on induction. Basic mathematical structures: finite and infinite sets, functions, Russell's paradox, the Hilbert's hotel example. (slides) 
Kenneth Rosen Chapter 2 
July 28 
Special lecture by Khushraj Madnani: Propositional logic, predicates and quantifiers, rules of inference.

Kenneth Rosen Chapter 1 
July 31 
Basic mathematical structures: types of functions, properties of finite and infinite sets through functions, countable sets and their properties. (slides)

Kenneth Rosen Chapter 2 
Aug 04 
Countable and uncountable sets, Cantor's diagonalization technique, Cantor's paradox, Continuum Hypothesis; Relations. (slides)

Kenneth Rosen Chapter 2 
Aug 05 
Representation and types of relations, equivalence relations and partitions, more examples. (slides)

Kenneth Rosen Chapter 7 
Aug 07 
Partial order relations: posets, chains, antichains, topological sorting, Mirsky's theorem, application to parallel task scheduling. (slides)

Kenneth Rosen Chapter 7 
Aug 11 
Recap of partial order relations, Mirsky's theorem, Statement of Dilworth's theorem. Introduction to counting and combinatorics, simple examples, some basic principles of counting. (slides)

Kenneth Rosen Chapter 7, Chapter 5 
Aug 12 
Basic counting techniques: sum and product principles, permutations and combinations, counting number of (ordered) subsets, double counting, Handshake lemma (slides)

Kenneth Rosen Chapter 5 
Aug 13 
Quiz 1


Aug 18 
Basic counting techniques: double counting and bijective principles, Cayley's theorem of labeled trees, binomial theorem (slides)

Kenneth Rosen Chapter 5++ 
Aug 19 
Binomial theorem, Fun with Pascal's triangle, permutation and combinations with repetitions, estimating n! (slides)

Kenneth Rosen Chapter 5 
Aug 21 
Recurrence relations, Fibonacci sequence, Catalan numbers, solving linear recurrences (slides)

Kenneth Rosen Chapter 6 
Aug 25 
Solving the Fibonacci recurrence and other linear recurrences, power series and generating functions(slides)

Kenneth Rosen Chapter 6 
Aug 26 
Generating functions: examples, properties, and applications. Solving the Catalan recurrence, counting, proving binomial identities (slides)

Kenneth Rosen Chapter 6 
Aug 28 
Principle of Inclusion and Exclusion and its applications: number of surjections, number of derangements (slides)

Kenneth Rosen Chapter 6 
Sept 01 
Quiz 2


Sept 01 
PigeonHole Principle and its applications (slides)

Kenneth Rosen Chapter 5 
Sept 02 
Variants of PigeonHole Principle, extensions of the coloring game, introduction to Ramsey theory (slides)

Kenneth Rosen Chapter 5++ 
Sept 04 
Introduction to Ramsey theory: proof of Ramsey's theorem for 2 colors, some more examples, Ramsey numbers. (slides)

++ 
  
Sept 10 
Midsem


  
Sept 15 
Bounds on Ramsey numbers, lower bound using the probabilistic method. Start of next topic: Graph theory, what are graphs, Konigsberg Bridge problem (slides)

++ 
Sept 16 
Introduction to Graph theory: basic terminology, Eulerian graphs and their characterization using degrees of vertices (slides)

Douglas West, Chapter 1, Section 1.1, 1.2 
Sept 18 
Eulerian graphs, bipartite graphs and their characterization using odd cycles (slides)

Douglas West, Chapter 1, Sections 1.1, 1.2 
Sept 22 
Bipartite graphs, subgraphs, cliques and independent sets, degree sum formula (slides)

Douglas West, Chapter 1, Sections 1.11.3 
Sept 23 
Finding large bipartite subgraphs, graph representations and isomorphism, some special graphs (slides)

Douglas West, Chapter 1, Sections 1.11.3 
Sept 24 
Graph isomorphism, Graph automorphism, connected components of a graph (slides)

Douglas West, Chapter 1, Sections 1.11.3 
Sept 25 
Connected components, cutedges, matchings (slides)

Douglas West, Chapter 1, Chapter 3 
Sept 29 
Perfect, maximal and maximum matchings, symmetric difference, characterization of maximum matchings using augmenting paths (slides)

Douglas West, Chapter 3, Section 3.1 
Sept 30 
Characterizing perfect matchings in bipartite graph: Hall's condition (slides)

Douglas West, Chapter 3, Section 3.1 
Oct 07 
Quiz 3


Oct 07 
Hall's theorem, matchings and vertex covers (slides)

Douglas West, Chapter 3, Section 3.1 
Oct 09 
Matchings and vertex covers: KonigEgervary theorem and applications (slides)

Douglas West, Chapter 3, Section 3.1 
Oct 13 
Stable matchings and the Gale Shapley algorithm (slides)

Douglas West, Chapter 3, Section 3.2 
Oct 14 
Start of next topic: Abstract algebra and Number theory, permutations and graph automorphisms, definition of a group (slides)

Norman Biggs, Chapter 20 
Oct 16 
Abstract algebra  groups: definitions, examples and simple properties (slides)

Norman Biggs, Chapter 20 
Oct 27 
Abstract algebra  symmetries of an equilateral triangle, Abelian groups, subgroups (slides)

Norman Biggs, Chapter 20 
Oct 28 
Abstract algebra  order of a group, cyclic groups, group isomorphisms (slides)

Norman Biggs, Chapter 20 
Oct 30 
Abstract algebra  Lagrange's theorem (slides)

Norman Biggs, Chapter 20 
Nov 01 
Abstract algebra  Some corollaries and applications of Lagrange's theorem (slides)

Norman Biggs, Chapter 20 
Nov 03 
Quiz 4


Nov 03 
Number theory and applications to cryptography  Modular arithmetic, DiffieHellman Key exchange protocol (slides)

Kenneth Rosen Chapter 3, ++ 
Nov 05 
Number theory and applications to cryptography  Some more modular arithmetic, Euler totient function, the RSA cryptosystem (slides)

Kenneth Rosen Chapter 3 