CS 70
Discrete Mathematics
for Computer Science

 Prof. Luca Trevisan

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

 

 


News


Textbook

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


 

Information

 


Work

 


Lectures

  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