Discrete Mathematics · August–November 2023
IIT Gandhinagar · ES214
Co-taught by Neeldhara Misra and Anirban Dasgupta. This introductory course covered proof, logic, sets, counting, graphs, probability, algebraic methods and number theory.
Published lecture schedule
| Date | Topic |
|---|---|
| 02 Aug, 2023 | 1. Intro to Proofs - I General Methods • Chessboard Tilings • Game of Chomp |
| 03 Aug, 2023 | 2. Intro to Proofs - II Pigeonhole Principle • Illustrative Examples |
| 08 Aug, 2023 | 3. Sets Definitions • Operations • Showing Containment • Showing Equality |
| 09 Aug, 2023 | 4. Functions and Relations Injections, Surjections, Bijections • Compositions • Equivalence Classes |
| 16 Aug, 2023 | 5. Induction Dominoes, Ladders, and Chips • Examples • Non-Examples • Strong Induction |
| 22 Aug, 2023 | 6. Propositional and Predicate Logic Syntax • Truth Tables • Quantifiers |
| 23 Aug, 2023 | 7. Inference Systems Inference Rules (e.g, Modus Ponens, Modus Tollens, Resolution, etc) • Paradoxes |
| 29 Aug, 2023 | 8. Elementary Counting Methods Permutations • Combinations • Binomial Coefficients |
| 30 Aug, 2023 | 9. The Method of Double Counting Examples of proofs by double-counting |
| 12 Sep, 2023 | 10. Intro to Graphs: Euler Tours Necessary and Sufficient Conditions for Euler Tours • Computing Euler Tours |
| 13 Sep, 2023 | 11. Hall's Theorem Matchings • Congestion in Bipartite Graphs • Hall's Theorem • Applications |
| 19 Sep, 2023 | 12. Graph Coloring Map Coloring • Greedy Algorithms • Bipartite Graphs • k-Degenerate Graphs |
| 20 Sep, 2023 | 13. Planarity Planar Graphs are Five-Colorable • Obstructions to Planarity |
| 26 Sep, 2023 | 14. Graphs Recap ~ |
| 27 Sep, 2023 | 15. Probability Intro Basics of Discrete Probability • Monty Hall • Conditional Probability |
| 03 Oct, 2023 | 16. The Probabilistic Method - I An Introduction to the Method • Applications in Graph Theory |
| 04 Oct, 2023 | 17. The Probabilistic Method - II Ramsey Number • Sum-Free Sets |
| 10 Oct, 2023 | 18. Recap ~ |
| 17 Oct, 2023 | 19. The Linear Algebra Method - I OddTown and EvenTown |
| 18 Oct, 2023 | 20. The Linear Algebra Method - II VC Dimension of a Set System • Sauer's Lemma |
| 31 Oct, 2023 | 21. Intro to Groups: Rotations and Symmetries TBA |
| 01 Nov, 2023 | 22. Permutation and Cyclic Groups TBA |
| 07 Nov, 2023 | 23. Homomorphisms TBA |
| 08 Nov, 2023 | 24. Quotient Groups and First Isomorphism Theorem TBA |
| 14 Nov, 2023 | 25. Intro to Number Theory: Extended Euclid's Algorithm TBA |
| 15 Nov, 2023 | 26. Chinese Remainder Theorem TBA |
| 21 Nov, 2023 | 27. Applications I: RSA TBA |
| 22 Nov, 2023 | 28. Applications II: PageRank TBA |
| 23 Nov, 2023 | 29. Recap ~ |
The table preserves the published plan, including entries whose descriptions were left as “TBA”. It is not independent evidence that each planned session took place.