Readings

  • I’m going to refer to two versions of lectures notes on Mathematics for Computer Science from MIT. The older version (LL below) is more succinct and easier to read for some topics in the course. The newer version (LLM below) is more detailed and contains additional material that will be useful for some topics we will cover.
  • LL = Mathematics for Computer Science lecture notes by Eric Lehman and Tom Leighton at MIT.
    Warning: this is a 339 page pdf file. You may want to print/view only selected sections mentioned below.
  • LLM = Mathematics for Computer Science lecture notes by Eric Lehman, Tom Leighton and Albert Meyer at MIT.
    Warning: this is a 556 page pdf file. You may want to print/view only selected sections mentioned below.
  • Some of the precise topics for future weeks and associated readings are subject to change.
  1. Mathematical Preliminaries
    • Proof techniques (Sep 17, 19)
    • Readings: LL Chapters 1-3
    • Estimating sums, Growth rate of functions
    • Readings: LLM Chapter 9  (superset of LL Chapters 10-11)
    • Recurrence Relations (Sep 24)
    • Readings: LLM Chapter 10
  2. Combinatorics and Probability(Sep 26, Oct 1, 3, 8, 11, 15)
    • Counting, permutations, binomial theorem. (Sep 26)
    • Readings: LLM Chapter 11
    • Probabilities, conjunction/disjunction of events, where intuition can go astray. (Oct 1)
    • Readings: LLM Chapter 14
    • Conditional probabilities, Bayes’s formula, independence. (Oct 3)
    • Readings: LLM Chapter 15, 16
    • Random variables, expectation, variance, deviation from the mean. (Oct 8,11, 15)
    • Readings: LLM Chapter 17, 18
  3. Sketching and streaming algorithms (Oct 17)
    • Streaming algorithms – estimating frequent elements: notes.
    • Hashing – universal hash functions: notes.
    • Min-wise Independent permutations: Min.
  4. Online algorithms (Oct 22, 24)
    • Online algorithms 1: Rent or Buy and List Update: online1_2011.
    • Online algorithms 2: Machine Scheduling and Learning from Experts: online2_2011.
    • Randomized Algorithm for Ski Rental Problem (notes by Claire Mathieu)
  5. Game Theory and Linear Programming (Nov 5, 7)
    • Two-player games, Nash equilibrium, Zero sum games
    • Intro to linear programming and duality
    • Existence of Nash equilibirum for 2-player zero-sum games via LP duality
    • Readings: notes posted on piazza
  6. Graph Theory I (Nov 12, 14)
    • Introduction to basic concepts.
    • Readings: LLM Sections 5.1, 5.3, 5.4, 5.5, 5.6.1, 5.6.2, 5.7
    • Minimum Spanning Tree: notes by Avrim Blum.
    • Sorting Lower Bound: notes by Avrim Blum.
    • Characterizations of Eulerian graphs (did not cover)
  7. Graph Theory II (Nov 19, 21)
    • Huffman Coding, Randomized algorithm for Min Cut, Matching, Hall’s theorem, stable marriage.
    • Readings: LLM Section 5.2 (for Hall’s theorem and stable marriage)
    • Huffman Coding: notes by David Wagner.
    • Randomized Min Cut: notes by Jeff Erickson.
    • Maximum Matching in bipartite graphs – alternate proof of Hall’s theorem (notes)
    • Maximum Matching in bipartite graphs using max-flow algorithm (see Chapter 7 of this book) (did not cover)
    • Stable Matching: Slides and a demo by Kevin Wayne.
  8. Cryptography(Nov 26, 28)
    • Introduction to cryptography (Chapter 1 of book by Katz and Lindell)
    • Readings:
    • Extended Euclid’s algorithm (Umesh Vazirani’s notes)
    • Chinese Remainder Theorem
    • RSA
    • Secret Sharing: notes by David Wagner.
    • Zero Knowledge: An entertaining non-technical illustration of zero-knowledge (The name of the character Mick Ali in the story is a play on Silvio Micali, one of the co-authors of the paper that introduced zero knowledge.)
  9. Intractability: Turing Machines, Undecidability and NP-Completeness (Dec 3,5,10,12)
    • Readings: COS 340 course packet.