CS 70
Discrete Mathematics
for Computer Science

 Prof. Luca Trevisan

Spring 2007
Tuesdays and Thursdays  3:30-5:00pm, 
2 LeConte





The lecture notes are the main reference. The following textbook is also recommended for further reading







  1. Jan 16, Lecture 1. Contents of the course. Boolean operations. [notes]

tentative schedule

Lectures 1-3: mathematical logic, proof techniques, proofs by induction

Lecture 4: the stable matching algorithm

Lectures 5-6:arithmetic algorithms, GCD

Lectures 7-8: polynomials and applications to cryptography

Lecture 9: error-correcting codes

Lectures 10-11: graph theory

Lectures 12-13: counting and basic probability

Lectures 14-15: conditional probability

Lectures 16-18: expectation, linearity of expectation, variance, concentration of probability

Lectures 19-21: IID random variables, Chernoff bounds, and applications

Lecture 22: power law distributions

Lecture 23-27: infinity, diagonalization and halting problem