CS70

CS 70 at UC Berkeley

Discrete Mathematics and Probability Theory

Lectures: T/Th 12:30-2 p.m., 150 Wheeler

Professor Babak Ayazifar

ayazifar (at) berkeley (dot) edu

Office Hours: TBD

Professor Satish Rao

satishr (at) cs.berkeley (dot) edu

Office Hours: M 3-4, Tu 4-5, 687 Soda

Week 0 Overview

Propositional Logic, Proofs

Discussions

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 00a: Propositional Logic (solution)
  • Discussion 00b: Proofs
  • Discussion 01a: Proofs, Induction
  • Discussion 01b: Induction, Well-Ordering Principle
  • Discussion 02a: Stable Marriage
  • Discussion 02b: Graph Theory I
  • Discussion 03a: Graph Theory II
  • Discussion 03b: Modular Arithmetic I
  • Discussion 04b: Modular Arithmetic II
  • Discussion 05a: RSA
  • Discussion 05b: Polynomials
  • Discussion 06a: Error-Correcting Codes
  • Discussion 06b: Countability, Computability
  • Discussion 07a: Counting, Combinatorial Proofs
  • Discussion 07b: Probability Spaces
  • Discussion 08a: Conditional Probability, Birthday Paradox, Bayes Rule
  • Discussion 08b: Bayes Rule, Independence, Binomial Distribution
  • Discussion 09b: Binomial Distribution, Expectation
  • Discussion 10a: Distributions, Variance
  • Discussion 10b: Variance, Joint Distributions
  • Discussion 11a: Variance, Continuous Probability I
  • Discussion 11b: Continuous Probability II
  • Discussion 12a: Continuous Probability III
  • Discussion 12b: Gaussians, Inequalities
  • Discussion 13a: CLT, Covariance
  • Discussion 14a: WLLN, Regression
  • Discussion 14b: Markov Chains, Fun
Expand

Homeworks

All homeworks are graded for accuracy and it is highly-recommended that you do them. Your lowest two homework scores will be dropped, but these drops 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.

  • Homework 00: Course Logistics (TeX)
  • Homework 01: Propositional Logic, Proofs
  • Homework 02: Induction, Stable Marriage
  • Homework 03: Graphs
  • Homework 04: Modular Arithmetic
  • Homework 05: RSA, Polynomials
  • Homework 06: Polynomials, Error-Correcting Codes
  • Homework 07: Countability, Computability, Counting
  • Homework 08: Combinatorial Proofs, Probability
  • Homework 09: Random Variables, Distributions
  • Homework 10: Expectation, Distributions
  • Homework 11: Variance, Continuous Probability
  • Homework 12: Continuous Probability
  • Homework 13: Gaussians, CLT, Regression
Expand

Lecture Slides

  • Lecture 1 (full) (6up): Introduction, Propositional Logic
  • Lecture 2 (full) (6up): Proofs/Induction (Draft)
  • Lecture 3: Proofs. Induction.
  • Lecture 4: Induction
  • Lecture 5: Stable Marriage
  • Lecture 6: Graphs
  • Lecture 7: Trees, Complete, Planar
  • Lecture 8: Planar, Mod. Arith. (Intro)
  • Lecture 9: GCD: Euclid
  • Lecture 10: EGCD; Midterm Review
  • Lecture 11: CRT: RSA (start)
  • Lecture 12: RSA: Signature Schemes
  • Lecture 13: Polynomials: Secret Sharing, Erasure Codes
  • Lecture 14: Erasure Codes, Error Correction
  • Lecture 15: Erasure Codes, Countability
  • Lecture 16: Countability/Undecidability
  • Lecture 17: Undecidability/Counting
  • Lecture 18: Counting
  • Lecture 19: Introduction to Probability
  • Lecture 20: Conditional Probability
  • Lecture 21: Conditional Probability, Bayes Rule
  • Lecture 22: Random Variables, Distributions
  • Lecture 23: Review
  • Lecture 24: Expectation
  • Lecture 25: Important Distributions
  • Lecture 26: Distributions, Variance
  • Lecture 27: Joint Distributions, Conditional Distributions
  • Lecture 28: Continuous Probability
  • Lecture 29: Continuous Probability II
  • Lecture 30: Continuous Probability III
  • Lecture 31: Gaussian RVs & CLT
  • Lecture 32: Inequalities
  • Lecture 33: Inequalities II, WLLN
  • Lecture 34: Linear Regression
  • Lecture 35: Linear Regression and Beyond
  • Lecture 36: Markov Chains I
  • Lecture 37: Markov Chains II
Expand