ES 214 | Aug-Nov 2023

ES214. Discrete Mathematics

August — November 2023

(co-instructor with Prof. Anirban Dasgupta.)

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.

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.

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

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

Venue: 1/101

Lectures:

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

Tutorials

  • Thursdays 3:30PM — 5:00PM

Office Hours: By email.

TAs:

  1. Harshil Mittal
  2. Saraswati Nanoti
  3. Eshwar Dhande
  • 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
~
No matching items

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)
No matching items