everything.study
18.310

Principles of Discrete Applied Mathematics

Undergraduate · Historical course

Fall 2013

Topics

  • Introduction
  • Probability Theory: Bayes’ Rule, Inclusion-Exclusion Formula, etc.
  • Pigeonhole Principle; Probabilistic Method
  • Probability Theory: Weak Law of Large Numbers
  • Chernoff Bounds
  • Sequential Choice / Optimal Stopping Theory
  • Counting, Coding, Sampling: Catalan Numbers, Bijective Proofs, etc.
  • Counting, Coding, Sampling: Coding
  • Generating Functions I
  • Writing : Information Order and Connectivity (Cohesion)
  • Generating Functions II
  • Generating Functions III
  • Linear Programming: Models
  • Linear Programming: Simplex Method
  • Linear Programming: Simplex Method (cont.)
  • Math : Simplex and Linear Programming Practice
  • Linear Programming: Duality
  • Network Flows: Maximum Flow, Augmenting Path Algorithm
  • Writing : Audiences, Explaining a Topic to an Informal Audience
  • Network Flows: Maximum Flow, Minimum Cut Theorem
  • Linear Programming: Zero-Sum Games
  • Sorting Algorithms
  • Median Finding and QUICKSORT
  • Median Finding and QUICKSORT(cont.)
  • Sorting Networks: Batcher’s Algorithm
  • Modular Arithmetic and Elementary Algebra
  • Modular Arithmetic and Elementary Algebra: Group Theory
  • Math : Euclid’s Algorithm & Number Theory
  • Cryptography: The RSA Code
  • Cryptography: Primality Testing
  • Math : Primality Testing & RSA
  • Factoring
  • FFT (Fast Fourier Transform) I
  • FFT II
  • Writing : Peer Critique
  • FFT for Multiplication
  • Shannon’s Information Theory
  • Huffman Codes
  • Lempel-Ziv Codes
  • Shannon’s Noisy Coding Theorem
  • Linear Codes
  • Polynomial Codes

Readings

Sources