Catalog

Principles of Discrete Applied Mathematics

Mathematics MIT CC BY-NC-SA 4.0 20 lectures

This course will teach you illustrative topics in discrete applied mathematics, including counting, generating functions, probability, linear optimization, algebraic structures, basic number theory, information theory, and coding theory. It is a {{% resource_link "8d257f11-e2b0-4925-8422-764c0519d33d" "CI-M" %}} (Communication Intensive in the Major) course and thus includes a writing component.

Syllabus

  1. 1 Lecture 1: Pigeonhole Principle
  2. 2 Lecture 2: Independence and Conditioning
  3. 3 Lecture 3: Inclusion-Exclusion
  4. 4 Lecture 4: Counting
  5. 5 Lecture 5: More Counting and Generating Functions
  6. 6 Lecture 6: More on Generating Functions
  7. 7 Lecture 7: Generating Functions for Catalan Numbers
  8. 8 Lecture 8: Tail Bounds
  9. 9 Lecture 9: Chernoff Bounds
  10. 10 Lecture 10: Modular Arithmetic
  11. 11 Lecture 11: Basic Group Theory
  12. 12 Lecture 12: Introduction to Linear Programming
  13. 13 Lecture 13: Duality in Linear Programming
  14. 14 Lecture 14: Zero-Sum Games
  15. 15 Lecture 15: Max-Flow Min-Cut Theorem
  16. 16 Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem
  17. 17 Lecture 17: Huffman Coding
  18. 18 Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem
  19. 19 Lecture 19: Error-Correcting Codes—Hamming Codes
  20. 20 Lecture 20: Reed-Solomon Codes

Course materials