Readings

• 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.

1. Mathematical Preliminaries
   • Proof techniques (Sept 23, 28, 30)
   • Readings: LL Chapters 1-3.
   • Estimating sums, Growth rate of functions
   • Readings: LL Chapter 10 (Sections 10.1 and 10.4.1), Chapter 11
2. Combinatorics and Probability (Oct 5, 7, 12, 14)
   • Counting, permutations, binomial theorem.
   • Probabilities, conjunction/disjunction of events.
   • Where intuition can go astray, combinatorial proof.
   • Conditional probabilities, Bayes's formula, independence,
   • Random variables, expectation, variance, Chebyshev's inequality.
   • Readings: LL Chapter 16.1, 16.2, 16.5, Chapter 18-24.
3. Advanced Hashing and Applications (week of Oct 19)
   • Notes on hashing
4. Online Algorithms (week of Oct 26)
   • Notes on move to front heuristic
   • More notes on move to front heuristic
5. Graph Theory (week of Nov 9)
   • Graph Theory
   • 5-color thm (Harary's "Graph Theory")
6. Cryptography (week of Nov 22)
   • One-Time Pad
   • Modular arithmetic and RSA
   • Digital signatures, fingerprinting, mental poker games
   • Notes on Cryptography - Lectures 2, 3, 6, 7, 15, 16, 20
   • More advanced material: Optional
   • Zero Knowledge
7. What can computers do and not do ?