News

• 1/02 The web site is up. See you on Wednesday, January 16

Textbook

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

• Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill, Inc., New York.
You do not need to buy the latest edition.

Information

• Course overview: prerequisites, grading, etc
• Instructor: Luca Trevisan. Email: luca@eecs. Office hours: Thursday 2-3pm, 679 Soda
• TAs
  • Alex Fabrikant. Email alexf@eecs. Office hours: Mondays 3-4pm, 511 Soda
  • Vahab Pournaghshband. Email vahab@berkeley. Office hours: Mondays 1-2pm, 511 Soda

Work

• Homeworks are due in the CS70 drop box in 283 Soda. The first homework will be out on January 23
  

• Handouts
  • Notes for Lectures 1 and 2
• Exams

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