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