# ES 214 | Aug-Nov 2023

## ES214. Discrete Mathematics

##### August — November 2023

(co-instructor with Prof. Anirban Dasgupta.)

All slides for the initial lectures can be found here.

Date | Lecture | Slides | Notes | Video |

02 Aug, 2023 |
1. Intro to Proofs - IGeneral Methods • Chessboard Tilings • Game of Chomp |
|||

03 Aug, 2023 |
2. Intro to Proofs - IIPigeonhole Principle • Illustrative Examples |
|||

08 Aug, 2023 |
3. SetsDefinitions • Operations • Showing Containment • Showing Equality |
|||

09 Aug, 2023 |
4. Functions and RelationsInjections, Surjections, Bijections • Compositions • Equivalence Classes |
|||

16 Aug, 2023 |
5. InductionDominoes, Ladders, and Chips • Examples • Non-Examples • Strong Induction |
|||

22 Aug, 2023 |
6. Propositional and Predicate LogicSyntax • Truth Tables • Quantifiers |
|||

23 Aug, 2023 |
7. Inference SystemsInference Rules (e.g, Modus Ponens, Modus Tollens, Resolution, etc) • Paradoxes |
|||

29 Aug, 2023 |
8. Elementary Counting MethodsPermutations • Combinations • Binomial Coefficients |
|||

30 Aug, 2023 |
9. The Method of Double CountingExamples of proofs by double-counting |
|||

12 Sep, 2023 |
10. Intro to Graphs: Euler ToursNecessary and Sufficient Conditions for Euler Tours • Computing Euler Tours |
|||

13 Sep, 2023 |
11. Hall's TheoremMatchings • Congestion in Bipartite Graphs • Hall's Theorem • Applications |
|||

19 Sep, 2023 |
12. Graph ColoringMap Coloring • Greedy Algorithms • Bipartite Graphs • k-Degenerate Graphs |
|||

20 Sep, 2023 |
13. PlanarityPlanar Graphs are Five-Colorable • Obstructions to Planarity |
|||

26 Sep, 2023 |
14. Graphs Recap~ |
|||

27 Sep, 2023 |
15. Probability IntroBasics of Discrete Probability • Monty Hall • Conditional Probability |
|||

03 Oct, 2023 |
16. The Probabilistic Method - IAn Introduction to the Method • Applications in Graph Theory |
|||

04 Oct, 2023 |
17. The Probabilistic Method - IIRamsey Number • Sum-Free Sets |
|||

10 Oct, 2023 |
18. Recap~ |
|||

17 Oct, 2023 |
19. The Linear Algebra Method - IOddTown and EvenTown |
|||

18 Oct, 2023 |
20. The Linear Algebra Method - IIVC Dimension of a Set System • Sauer's Lemma |
|||

31 Oct, 2023 |
21. Intro to Groups: Rotations and SymmetriesTBA |
|||

01 Nov, 2023 |
22. Permutation and Cyclic GroupsTBA |
|||

07 Nov, 2023 |
23. HomomorphismsTBA |
|||

08 Nov, 2023 |
24. Quotient Groups and First Isomorphism TheoremTBA |
|||

14 Nov, 2023 |
25. Intro to Number Theory: Extended Euclid's AlgorithmTBA |
|||

15 Nov, 2023 |
26. Chinese Remainder TheoremTBA |
|||

21 Nov, 2023 |
27. Applications I: RSATBA |
|||

22 Nov, 2023 |
28. Applications II: PageRankTBA |
|||

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.