Catalog

Mathematics for Computer Science

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 25 lectures

This course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.

Syllabus

  1. 1 Lecture 1: Introduction and Proofs
  2. 2 Lecture 2: Induction
  3. 3 Lecture 3: Strong Induction
  4. 4 Lecture 4: Number Theory I
  5. 5 Lecture 5: Number Theory II
  6. 6 Lecture 6: Graph Theory and Coloring
  7. 7 Lecture 7: Matching Problems
  8. 8 Lecture 8: Graph Theory II: Minimum Spanning Trees
  9. 9 Lecture 9: Communication Networks
  10. 10 Lecture 10: Graph Theory III
  11. 11 Lecture 11: Relations, Partial Orders, and Scheduling
  12. 12 Lecture 12: Sums
  13. 13 Lecture 13: Sums and Asymptotics
  14. 14 Lecture 14: Divide and Conquer Recurrences
  15. 15 Lecture 15: Linear Recurrences
  16. 16 Lecture 16: Counting Rules I
  17. 17 Lecture 17: Counting Rules II
  18. 18 Lecture 18: Probability Introduction
  19. 19 Lecture 19: Conditional Probability
  20. 20 Lecture 20: Independence
  21. 21 Lecture 21: Random Variables
  22. 22 Lecture 22: Expectation I
  23. 23 Lecture 23: Expectation II
  24. 24 Lecture 24: Large Deviations
  25. 25 Lecture 25: Random Walks

Course materials