CS 70 at UC Berkeley

Discrete Mathematics and Probability Theory

Lectures: M/T/W/Th 2-3:30 p.m., 155 Dwinelle

Instructor Hongling Lu

hongling_lu (at) berkeley (dot) edu

Office Hours: T/Th 12-1 p.m., 611 Soda

Instructor Vrettos Moulos

vrettos (at) berkeley (dot) edu

Office Hours: W 4-5 p.m., F 2:30-3:30 p.m., 212 Cory

Instructor Allen Tang

chen.tang (at) berkeley (dot) edu

Office Hours: M/W 12-1 p.m., 212 Cory

Week 2 Overview

Stable Marriage, Graph Theory, Countability, Computability


The discussion sections will not cover new material, but rather will give you additional practice solving problems. You can attend any discussion section you like. However, if there are fewer desks than students, then students who are officially enrolled in that section will get seating priority. See Syllabus for more information.

  • Discussion 01a: Propositional Logic (solution)
  • Discussion 01b: Proofs (solution)
  • Discussion 01c: Induction (solution)
  • Discussion 01d: Induction (solution)
  • Discussion 02a: Graph Theory
  • Discussion 02b: Graph Theory
  • Discussion 02c:
  • Discussion 02d:
  • Discussion 03a: Modular Arithmetic
  • Discussion 03b: Modular Arithmetic, Bijections
  • Discussion 04a: Fermat's Little Theorem, RSA
  • Discussion 04b: Polynomials
  • Discussion 05a: Lagrange Interpolation, Erasure Codes, Secret Sharing
  • Discussion 05b: Berlekamp-Welch
  • Discussion 06a: Uncountability, Uncomputability
  • Discussion 06b: Counting
  • Discussion 07a: Basic Probability
  • Discussion 07b: Conditional Probability
  • Discussion 08a: Random Variables, Binomial Distribution
  • Discussion 08b: Union Bound, Geometric Distribution, Poisson Distribution


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. See Syllabus for more information.

  • Homework 00: Course Logistics (TeX)
  • Homework 01: Propositional Logic, Proofs, Induction (TeX)
  • Homework 02: Induction, Stable Marriage, Graph Theory
  • Homework 03: Graph Theory
  • Homework 04: Modular Arithmetic
  • Homework 05: Chinese Remainder Theorem, RSA, Polynomials
  • Homework 06: Polynomials, Secret Sharing, Error Correcting Codes, Uncountability
  • Homework 07: Uncountability, Uncomputability, Counting
  • Homework 08: Combinatorial Proofs, Probability Spaces, Conditional Probability, Independence