Course contents

Textbook References



Supplementary Reading

Topics covered

  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, well-ordering principle.   Kenneth Rosen Chapter 1, Chapter 4
  July 23   Well-ordering 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, anti-chains, topological sort, applications to (parallel) task scheduling.   Kenneth Rosen Chapter 7
  Aug 10   Basic mathematical structures: chains, anti-chains, 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: Pigeon-hole principle (PHP), its variants and its applications   Kenneth Rosen Chapter 5
  Aug 29   Quiz 2  
  Aug 31   Counting techniques: Pigeon-hole 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 Konig-Egervary 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 Diffie-Hellman protocol.   Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++
  Nov 3   Abstract algebra and Number theory: Applications to cryptography, Euler-totient function, the RSA protocol.   Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++

Notes: