Date 
Topics covered 
Reference in Textbook

July 18 
Introduction, propositions, predicates, examples of theorems and proofs. (slides) 
Kenneth Rosen Chapter 1 
July 19 
Types of proof techniques. Axioms. Mathematical induction, examples. (slides) 
Kenneth Rosen Chapter 1, Chapter 4 
July 21 
Wellordering principle, Strong Induction. (slides) 
Kenneth Rosen Chapter 4 
July 25 
Basic mathematical structures: sets, Russell's paradox, infinite sets, functions. (slides) 
Kenneth Rosen Chapter 2++ 
July 26 
Basic mathematical structures: sets, functions, comparing infinite sets using functions. (slides) 
Kenneth Rosen Chapter 2++ 
July 28 
Pop quiz, Basic mathematical structures: countable and countably infinite sets. (slides) 
Kenneth Rosen Chapter 2++ 
Aug 1 
Basic mathematical structures: countable and uncountable sets, Continuum hypothesis. Relations. (slides) 
Kenneth Rosen Chapter 2++, Chapter 7 
Aug 2 
Basic mathematical structures: relations, equivalence relations and partitions of a set. (slides) 
Kenneth Rosen Chapter 7 
Aug 4 
Basic mathematical structures: more on equivalence relations, partial order relations, posets. (slides) 
Kenneth Rosen Chapter 7 
Aug 8 
Basic mathematical structures: posets, chains, antichains, topological sort, applications to (parallel) task scheduling. (slides) 
Kenneth Rosen Chapter 7 
Aug 9 
Basic mathematical structures: chains, antichains, lattices. (slides) 
Kenneth Rosen Chapter 7 
Aug 9 
Quiz 1 

Aug 11 
Lattices and on to Counting techniques: product and sum principles, the bijection principle. (slides) 
Kenneth Rosen Chapter 7, Chapter 5 
Aug 16 
Counting techniques: double counting, Handshake lemma, the binomial theorem, Pascal's triangle. (slides) 
Kenneth Rosen Chapter 5 
Aug 16 
Counting techniques: permutations and combinations with and without repetitions, estimating factorials (slides) 
Kenneth Rosen Chapter 5 
Aug 18 
Counting techniques: recurrence relations (slides) 
Kenneth Rosen Chapter 6. 
Aug 29 
Counting techniques: Solving recurrence relations (slides) 
Kenneth Rosen Chapter 6 
Aug 30 
Counting techniques: Solving recurrence relations via generating functions (slides) 
Kenneth Rosen Chapter 6 
Sep 01 
Counting techniques: Applications of generating functions, Principle of Inclusion Exclusion and its applications (slides) 
Kenneth Rosen Chapter 6 
Sep 01 
Counting techniques: Pigeonhole principle (PHP), its variants and its applications (slides) 
Kenneth Rosen Chapter 5 



Sep 07 
Midsem 




Sep 15 
Applications and Extensions of PHP to the coloring game (slides) 
Kenneth Rosen Chapter 5++ 
Sep 19 
Extensions of PHP  a glimpse of Ramsey theory (slides) 
Kenneth Rosen Chapter 5++ 
Sep 20 
Graph theory: Basic terminology, Konigsberg bridge problem, Eulerian graphs (slides) 
Douglas West, Chapter 1 
Sep 22 
Graph theory: Eulerian graphs and a characterization (slides) 
Douglas West, Chapter 1 
Sep 22 
Graph theory: Bipartite graphs and a characterization (slides) 
Douglas West, Chapter 1 
Sep 26 
Graph theory: Representation of graphs, Graph isomorphism (slides) 
Douglas West, Chapter 1 
Sep 27 
Graph theory: Subgraphs, cliques and independent sets (slides) 
Douglas West, Chapter 1 
Sep 27 
Quiz 2 

Sep 29 
Graph theory: large bipartite subgraphs, connected components, cut edges (slides) 
Douglas West, Chapter 1 
Oct 3 
Graph theory: Matchings, Perfect and maximum matchings, Augmenting paths (slides) 
Douglas West, Chapter 3 
Oct 4 
Graph theory: Characterization of maximum matchings using Augmenting paths (slides) 
Douglas West, Chapter 3 
Oct 6 
Graph theory: Characterization of perfect matchings in bipartite graphs  Hall's theorem and some applications (slides) 
Douglas West, Chapter 3 
Oct 17 
Graph theory: Minimum vertex covers and the KonigEgervary theorem (slides) 
Douglas West, Chapter 3 
Oct 18 
Graph theory: Stable matchings and the Gale Shapley algorithm (slides) 
Douglas West, Chapter 3 
Oct 20 
Start of next topic: Abstract algebra and Number theory, permutations and graphs automorphisms, definition of an abstract group, examples. (slides) 
Norman Biggs, Chapter 20 
Oct 24 
Abstract algebra and Number theory: More examples of groups, some simple properties, subgroups. (slides) 
Norman Biggs, Chapter 20 
Oct 25 
Abstract algebra and Number theory: subgroups of a group; special types of groups: Abelian and cyclic groups. (slides) 
Norman Biggs, Chapter 20 
Oct 25 
Quiz 3 

Oct 27 
Abstract algebra and Number theory: cyclic groups, isomorphisms of a group. (slides) 
Norman Biggs, Chapter 20 
Oct 27 
Abstract algebra and Number theory: order of subgroups of a group, Lagrange's theorem. (slides) 
Norman Biggs, Chapter 20 
Nov 3 
Abstract algebra and Number theory: Modular arithmetic and applications to cryptography; the DiffieHellman protocol. (slides) 
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ 
Nov 4 
Abstract algebra and Number theory: Applications to cryptography, Eulertotient function, the RSA protocol. (slides) 
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ 