ES 214 | Aug-Nov 2023

ES214. Discrete Mathematics

August — November 2023

(co-instructor with Prof. Anirban Dasgupta.)

About the Course

This is a first course in discrete mathematics and has a broad scope: we introduce elementary concepts in logic, set theory, combinatorics, graph theory, number theory, and probability. The course is designed to be accessible to students from all disciplines, and is a core course for the B.Tech. program at IITGN. We hope that students taking this course discover the beauty of mathematical methods and their applications.

Target Audience

You will find this course interesting if:

you think counting the number of ways in which you can complete your graduation requirements is a fun problem to think about,
you enjoy logic puzzles like this one or probability puzzles like this one, or
you like box-stacking challenges, or
you are enrolled in a program for which this course is in the core.

Prerequisites

This course is self-contained and involves no pre-requisites.

References

Discrete Mathematics and Its Applications by Kenneth Rosen
Open Textbook on Discrete Mathematics
Proofs: A Long-Form Mathematics Textbook by Jay Cummings
Playing with Discrete Math by Kyle Burke and Craig Tennenhouse
Online Course (with lecture videos): Math 4190, Summer I 2019

Timings and Venue

Venue: 1/101

Lectures:

Tuesdays 3:30PM — 5:00PM
Wednesdays 11:30 — 12:50

Tutorials

Thursdays 3:30PM — 5:00PM

TAs and Office hours

Office Hours: By email.

TAs:

Harshil Mittal
Saraswati Nanoti
Eshwar Dhande

Evaluation policy

Each of the three exams account for 20% of the grade.
Each of the eleven tutorials will have a quiz worth 5 points. The total number of points you can earn through quizzes is capped at 40, and accounts for 40% of the grade.
There will be weekly assignments that are not graded but are recommended for practice.

For IITGN students, (pre-)register through IMS as usual.
All quizzes and exams will be on Mathmatize; please sign up here.
For announcements, please sign up on Google classroom with this link or use the invite code nzl3hkr.
If you are not from IITGN and are interested in taking up the course, then please send us an email.

All slides for the initial lectures can be found here.

Date	Lecture	Slides	Notes	Video
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 ~

Weekly practice problems are posted to Google Classroom. There is no need to submit these assignments, but please make sure to get feedback from your peers, instructors and TAs as you go along. We also strongly encourage you to explore the problems from the courses available through Brilliant (access details have been shared on Google Classroom as well).

Problems and solutions for weekly quizzes are available from within Mathematize.

Issued	Assessment	Problems	Solutions	Due
TBA	Exam 1 Syllabus: topics in lectures 1 to 9 (inclusive)			-
TBA	Exam 2 Syllabus: topics in lectures 10 to 18 (inclusive)			-
TBA	Exam 3 Syllabus: topics in lectures 21 to 26 (inclusive)			-