Course contents
- We will study the following topics in this course:
Proofs and reasoning
Basic discrete structures
Counting and combinatorics
Elements of graph theory
Textbook References
- Discrete Mathematics and its applications with combinatorics and graph theory, by Kenneth H Rosen. Special Indian Edition published by Tata McGraw-Hill, 7th edition
- Introduction to Graph Theory, 2nd Edition, by Douglas B West. Eastern Economy Edition published by PHI Learning Pvt Ltd.
- Discrete Mathematics, 2nd Edition, by Norman L Biggs. Indian Edition published by Oxford University Press.
Supplementary Reading
- Logicomix: An epic search for truth, by Apostolos Doxiadis, Christos H. Papadimitriou, Alecos Papadatos and Annie Di Donna. International Edition published by Bloomsbury Publishing, 2009. -- A graphic novel about logic, madness, Bertrand Russell and the foundations of mathematics.
Topics covered
Chapter numbers written below are for the 7th edition of Kenneth H Rosen's book, Special Indian Edition published by Tata McGraw-Hill. In other editions, the chapter numbers may be different!| Date | Topics covered | Reference in Textbook |
|---|---|---|
| July 29 | Proofs and Reasoning: Introduction, propositions, propositional calculus, Boolean algebra. (slides) | Kenneth Rosen Chapter 1 |
| Aug 01 | Proofs and Reasoning: Propositional equivalence, Predicates and Quantifiers. (slides) | Kenneth Rosen Chapter 1 |
| Aug 05 | Proofs and Reasoning: Different types of proof techniques, Mathematical Induction. (slides) | Kenneth Rosen Chapter 1, Chapter 4 |
| Aug 08 | Proofs and Reasoning: Induction examples, Well-ordering principle. (slides) | Kenneth Rosen Chapter 4 |
| Aug 12 | Proofs and Reasoning: Strong Induction, more examples on Induction. (slides) | Kenneth Rosen Chapter 4 |
| Aug 19 | Basic mathematical structures: sets, examples, Russell's paradox. Functions. (slides) | Kenneth Rosen Chapter 2 |
| Aug 22 | Basic mathematical structures: functions, comparing infinite sets using functions, countable and countably finite sets. (slides) | Kenneth Rosen Chapter 2 |
| Aug 26 | Basic mathematical structures: countable and uncountable sets. Diagonalization (slides) | Kenneth Rosen Chapter 2 |
| Aug 28 | Quiz 1 | |
| Aug 29 | Basic mathematical structures: relations, partitions of a set, equivalence relations, classes (slides) | Kenneth Rosen Chapter 7 |
| Sept 02 | Basic mathematical structures: partial order relations, posets, chains, anti-chains. (slides) | Kenneth Rosen Chapter 7 | Sept 09 | Basic mathematical structures: topological sort, parallel-task scheduling, Mirsky's theorem, glb/lub, lattices. (slides) | Kenneth Rosen Chapter 7 |
| Sept 12 | Finishing Lattices, Counting techniques: product and sum principles, the bijection principle, double counting, Handshake lemma. (slides) | Kenneth Rosen Chapter 5 |
| Sept 20 | Midsem | |
| Sept 23 | Counting techniques: Pascal's triangle, Path counting, Permutations and combinations with repetitions. (slides) | Kenneth Rosen Chapter 5 |
| Sept 26 | Counting techniques: Estimating factorials, Recurrence relations and how to solve them, Fibonacci sequence and Catalan numbers. (slides) | Kenneth Rosen Chapter 6 |
| Sep 30 | Counting techniques: Solving recurrence relations via generating functions, Other applications of generating functions. (slides) | Kenneth Rosen Chapter 6 |
| Oct 03 | Counting techniques: Principle of Inclusion Exclusion (PIE) and its application, Pigeon-hole Principle (PHP) and its variants. (slides) | Kenneth Rosen Chapter 5 |
| Oct 07 | Counting techniques: PHP and its applications. Coloring game and a glimpse of Ramsey theory (slides) | Kenneth Rosen Chapter 5++ |
| Oct 10 | Graph theory: Basic terminology, Konigsberg bridge problem, Eulerian graphs and a characterization (slides) | Douglas West, Chapter 1 |
| Oct 14 | Graph theory: Bipartite graphs and a characterization via absence of odd cycles. (slides) | Douglas West, Chapter 1 | Oct 17 | Graph theory: Representation of graphs, Graph isomorphisms, cliques and independent sets, connected components. (slides) | Douglas West, Chapter 1 |
| Oct 23 | Quiz 2 | |
| Oct 24 | Graph theory: Matchings, Perfect and Maximum matchings; Characterization using Augmenting paths (slides) | Douglas West, Chapter 3 |
| Oct 27 | Graph theory: Characterization of perfect matchings in bipartite graphs - Hall's theorem and its applications (slides) | Douglas West, Chapter 3 |
| Oct 28 | Graph theory: Minimum vertex covers and the Konig-Egervary theorem, Stable Matchings (slides) | Douglas West, Chapter 3 |
| Oct 31 | Graph theory: Stable matchings and the Gale Shapley algorithm (slides). Extra Topic on Groups, Modular Arithmetic and Cryptography (slides by Prof. Sruthi Sekar). |
Douglas West, Chapter 3 |
Notes:
- Being a core CSE department course, CS105 will not be open for non-CSE students this semester. Interested non-CSE students are advised to consider one of the relevant minor courses being offered by the CSE dept this semester.