CS70

CS 70 at UC Berkeley

Discrete Mathematics and Probability Theory

Lecture: TuTh 3:30-5:00pm, Wheeler 150

Professor Alistair Sinclair

sinclair (at) berkeley (dot) edu

Office Hours: M 1:15-2:15PM, W 1:15-2:15PM, 677 Soda Hall

Professor Yun S. Song

yss (at) berkeley (dot) edu

Office Hours: W 11am-12pm, 629 Soda Hall; Th 5:15-6:15pm, 304B Stanley Hall

Week 0 Overview

Welcome to CS70!

Week 1 Overview

Propositional Logic, Proofs, Induction

Week 2 Overview

Stable Marriage, Graph Theory

Week 3 Overview

Graph Theory, Modular Arithmetic

Week 4 Overview

Public Key Cryptography, Polynomials

Week 5 Overview

Error Correcting Codes, Countability

Week 6 Overview

Midterm 1, Counting

Week 7 Overview

Counting

Week 8 Overview

Introduction to Probability, Conditional Probability

Week 9 Overview

Conditional Probability, Random Variables I

Week 10 Overview

Random Variables II, Concentration Inequalities, Law of Large Numbers

Week 11 Overview

Midterm 2, Hashing and Load Balancing

Week 12 Overview

Geometric and Poisson, Continuous Probability Distributions

Week 13 Overview

Continuous Probability Distributions, Thanksgiving Break

Week 14 Overview

Markov Chains, Decidability

Discussions

The discussion sections are specifically designed to consolidate the material covered in lectures and in the notes. It is highly recommended that you attend both discussions each week. You may attend any discussion section, but we recommend that you settle on a weekly two-section pair (with the same TA) as early as possible in the semester. If a particular section is too full, then students will be admitted on a first-come first-served basis and others will have to attend an alternative section. All sections are equivalent: they all cover the same material. See Policies for more information.

Expand

Homeworks

There will be weekly required homeworks, again designed to consolidate your understanding of the course material. It is highly recommended that you attempt all homeworks. Your lowest two homework scores will be dropped, but these drops should be reserved for emergencies. No additional allowances will be made for late or missed homeworks: please do not contact us about missed homeworks or late submissions. See Policies for more information.

Expand

Lecture Schedule

  • Lecture 1 (8/29): Introduction & Logic (Note 1)
  • Lecture 2 (9/3): Proofs (Note 2)
  • Lecture 3 (9/5): Induction (Note 3)
  • Lecture 4 (9/10): Stable Marriage (Note 4)
  • Lecture 5 (9/12): Graphs I (Note 5)
  • Lecture 6 (9/17): Graphs II (Note 5)
  • Lecture 7 (9/19): Modular Arithmetic (Note 6)
  • Lecture 8 (9/24): Public Key Cryptography: RSA (Note 7)
  • Lecture 9 (9/26): Polynomials (Note 8)
  • Lecture 10 (10/1): Error-Correcting Codes (Note 9)
  • Lecture 11 (10/3): Countability (Note 10)
  • Lecture 12 (10/15): Counting I (Note 11)
  • Lecture 13 (10/17): Counting II (Note 11)
  • Lecture 14 (10/22): Introduction to Probability (Note 12)
  • Lecture 15 (10/24): Conditional Probability (Note 13)
  • Lecture 16 (10/24): Combinations of Events (Note 13)
  • Lecture 17 (10/29): Random Variables I (Note 14)
  • Lecture 18 (11/5): Random Variables II (Note 15)
  • Lecture 19 (11/7): Concentration Inequalities and LLN (Note 16)
  • Lecture 20 (11/14): Applications (Note 17)
  • Lecture 21 (11/19): Geometric and Poisson Distributions (Note 18)
  • Lecture 22 (11/21): Continuous Distributions I (Note 19)
  • Lecture 23 (11/26): Continuous Distributions II (Note 19)
  • Lecture 24 (12/3): Finite Markov Chains (Note 20)
  • Lecture 25 (12/5): Self-Reference and Uncomputability (Note 21)