CS 70
Discrete Mathematics for Computer Science Prof. Luca Trevisan Spring 2007


The lecture notes are the main reference. The following textbook is also recommended for further reading
tentative schedule
Lectures 13: mathematical logic, proof techniques, proofs by induction
Lecture 4: the stable matching algorithm
Lectures 56:arithmetic algorithms, GCD
Lectures 78: polynomials and applications to cryptography
Lecture 9: errorcorrecting codes
Lectures 1011: graph theory
Lectures 1213: counting and basic probability
Lectures 1415: conditional probability
Lectures 1618: expectation, linearity of expectation, variance, concentration of probability
Lectures 1921: IID random variables, Chernoff bounds, and applications
Lecture 22: power law distributions
Lecture 2327: infinity, diagonalization and halting problem