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

Week 6 Overview

Covariance, Tail Sum, Coupon Collector's Problem

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)