MIT 6.1200J Mathematics for Computer Science, Spring 2024
This course covers elementary discrete mathematics for science and engineering, with a focus on mathematical tools and proof techniques useful in computer science. Topics include logical notation, sets, relations, elementary graph theory, state machines and invariants, induction and proofs by contradiction, recurrences, asymptotic notation, elementary analysis of algorithms, elementary number theory and cryptography, permutations and combinations, counting tools, and discrete probability.
- Lecture 1: Predicates, Sets, and Proofs
- Lecture 2: Contradiction and Induction
- Problem Set 01
- Lecture 3: Casework and Strong Induction
- Lecture 4: State Machines
- Problem Set 02
- Lecture 5: Sums
- Problem Set 03
- Lecture 6: Asymptotics
- Lecture 7: Recurrences
- Problem Set 04
- Lecture 8: Divisibility
- Lecture 9: Modular Arithmetic
- Lecture 10: Cryptography
- Problem Set 05
- Lecture 11: Graphs and Coloring
- Lecture 12: Matching
- Problem Set 06
- Lecture 13: Connectivity and Trees
- Lecture 14: Digraphs and DAGs
- Problem Set 07
- Lecture 15: Relations and Counting
- Problem Set 08
- Lecture 16: Counting Techniques
- Lecture 17: More Counting Techniques
- Lecture 18: Probability
- Lecture 19: Conditional Probability
- Problem Set 09
- Lecture 20: Independence
- Lecture 21: Random Variables
- Lecture 22: Expectation
- Problem Set 10
- Lecture 23: Expectation and Variance
- Lecture 24: Large Deviations: Chebyshev and Chernov Bound, Wrap Up