Principles of Discrete Applied Mathematics

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

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