Fall 2012, Dept of Computer Science, Princeton University
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.
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
Combinatorics and Probability(Sep 26, Oct 1, 3, 8, 11, 15)
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.)
Intractability: Turing Machines, Undecidability and NP-Completeness (Dec 3,5,10,12)