# 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 - 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~ |

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 1Syllabus: topics in lectures 1 to 9 (inclusive) |
- | ||

TBA |
Exam 2Syllabus: topics in lectures 10 to 18 (inclusive) |
- | ||

TBA |
Exam 3Syllabus: topics in lectures 21 to 26 (inclusive) |
- |