| 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 |
Well-ordering 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, anti-chains, topological sort, applications to (parallel) task scheduling. (slides) |
Kenneth Rosen Chapter 7 |
Aug 9 |
Basic mathematical structures: chains, anti-chains, 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: Pigeon-hole 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 Konig-Egervary 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 Diffie-Hellman protocol. (slides) |
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ |
| Nov 4 |
Abstract algebra and Number theory: Applications to cryptography, Euler-totient function, the RSA protocol. (slides) |
Norman Biggs, Chapter 13, Kenneth Rosen, Chapter 3 ++ |