CS 70 at UC Berkeley

Discrete Mathematics and Probability Theory

Lectures: M/Tu/W/Th 2-3:30 pm, 155 Dwinelle

Instructor Sinho Chewi

chewisinho (at) berkeley (dot) edu

Office Hours: F 4:30-6 pm, 611 Soda

Instructor Vrettos Moulos

vrettos (at) berkeley (dot) edu

Office Hours: F 1-3 pm, 611 Soda


All homeworks are graded for accuracy and it is highly-recommended that you do them. Your lowest homework score will be dropped, but this drop should be reserved for emergencies. The TeX files we provide are not meant to be compiled. They are just provided as a reference. See Syllabus for more information.


Lecture Slides

The lecture schedule can be found here. We recommend reading the notes in advance.

  • Lecture 1: Introduction, Propositional Logic, First-Order Logic (full) (6up)
  • Lecture 2: Proofs (full) (6up)
  • Lecture 3: Induction (full) (6up)
  • Lecture 4: Well Ordering Principle, Induction, Graph Theory (Eulerian Tours) (full) (6up)
  • Lecture 5: Graph Theory (Trees, Planarity) (full) (6up)
  • Lecture 6: Graph Theory (Planarity, Coloring, Hypercubes), Modular Arithmetic (Multiplicative Inverses) (full) (6up)
  • Lecture 7: Bijections, Modular Arithmetic (Multiplicative Inverses, Euclid's Algorithm) (full) (6up)
  • Lecture 8: Modular Arithmetic (Euler's Totient Function, Fermat's Little Theorem), One-Time Pad, RSA, Digital Signatures (full) (6up)
  • Lecture 9: Modular Arithmetic (Chinese Remainder Theorem), Polynomials (Roots, Lagrange Interpolation) (full) (6up)
  • Lecture 10: Secret Sharing, Error Correction (Reed-Solomon Codes, Hamming Distance, Berlekamp-Welch Decoding) (full) (6up)
  • Lecture 11: Countability, Diagonalization (full) (6up)