ES 214 | Aug-Nov 2023
ES214. Discrete Mathematics
August — November 2023
(co-instructor with Prof. Anirban Dasgupta.)
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 ~ |
These are the weekly practice problems. 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.
Issued | Assessment | Problem Set | Solutions | Due |
10 Aug, 2023 |
Sets and Functions |
|||
17 Aug, 2023 |
Induction |
|||
24 Aug, 2023 |
Logic |
|||
31 Aug, 2023 |
Counting |
|||
14 Sep, 2023 |
Graphs I |
|||
21 Sep, 2023 |
Graphs II |
|||
05 Oct, 2023 |
Probability |
|||
19 Oct, 2023 |
Dimensionality Arguments |
|||
02 Nov, 2023 |
Groups I |
|||
09 Nov, 2023 |
Groups II |
|||
16 Nov, 2023 |
Number Theory |
Issued | Assessment | Problem Set | 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) |
- |