CS70

Spring 2017 CS70 at UC Berkeley

Discrete Mathematics and Probability Theory

Lectures: TTh 12:30 - 2:00 p.m., Pauley Ballroom

Professor Satish Rao

satishr@eecs (dot) berkeley (dot) edu

Office Hours: TBA

Week 0 Overview

Propositional Logic and 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: Prop. Logic, Proofs (solution)
  • Discussion 00b: Proofs (solution)
  • Discussion 01a: Prop. Logic, Proofs
  • Discussion 01b: Induction
  • Discussion 02a: Induction, SMA
  • Discussion 02b: Strong Induction, SMA
  • Discussion 03a: Graph Theory
  • Discussion 03b: Graph Theory
  • Discussion 04b: Modular Arithmetic
  • Discussion 05a: Bijections, RSA
  • Discussion 05b: Fermat's Little Theorem
  • Discussion 06a: Polynomials
  • Discussion 06b: Error Correction
  • Discussion 07a: Countability, Computability
  • Discussion 07b: Counting
  • Discussion 08a: Basic Probability
  • Discussion 08b: Conditional Probability
  • Discussion 09b: Probability, Independence
  • Discussion 10a: Random Variable, Expectation
  • Discussion 10b: Variance, Inequalities
  • Discussion 11a: LLN, LLSE
  • Discussion 11b: Conditional Expectation
  • Discussion 12a: Markov Chain I
  • Discussion 12b: Markov Chains II
  • Discussion 13a: Continuous Probability I
  • Discussion 14a: Continuous Probability II
  • Discussion 14b: Continuous Probability III
Expand

Homeworks

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: Prop. Logic, Proofs (Tex)
  • Homework 01: Proofs, Induction (Tex)
  • Homework 02: Induction, SMA
  • Homework 03: SMA, Graph
  • Homework 04: Modular Arithmetic
  • Homework 05: Modular Arithmetic, RSA
  • Homework 06: Polynomial
  • Homework 07: Countability
  • Homework 08: Counting
  • Homework 09: Basic Probability
  • Homework 10: Random Variable
  • Homework 11: Inequalities etc.
  • Homework 12: Conditional Expectation
  • Homework 13: Markov Chain, Continuous Probability
  • Homework 14: Continuous Probability
Expand

Lecture Slides

Slides generally follow the notes. Lecture videos are provided via CalCentral. See Syllabus for more information.

  • Lecture 1 (full) (6up): Propositional Logic
  • Lecture 2 (full) (6up): Proofs
  • Slide 3: Induction
  • Slide 4: Strong Induction
  • Slide 5: Stable Marriage Algorithm
  • Slide 6: Graph Theory
  • Slide 7: Graph Theory II
  • Slide 8: Modular Arithmetic
  • Slide 9: EGCD, Multiplicative Inverses
  • Slide 10: Midterm 1 Review
  • Slide 11: Bijections, RSA
  • Slide 12: Fermat's Little Theorem
  • Slide 13: Polynomial
  • Slide 14: Polynomials, Error Correcting
  • Slide 15: Berlekamp Welch
  • Slide 16: Uncountability
  • Slide 17: Computability
  • Slide 18: Counting
  • Slide 19: Midterm 2 Review (Discrete Math)
  • Slide 20: Probability Space
  • Slide 21: Conditional Probability
  • Slide 22: Bayes Rule
  • Slide 23: Bayes Rule, Independence
  • Slide 24: Midterm 2 Review (Probability)
  • Slide 25: Random Variables
  • Slide 26: Expectation
  • Slide 27: Coupons, Independent Random Variables
  • Slide 28: Variance, Inequalities, WLLN
  • Slide 29: Confidence Intervals
  • Slide 30: Linear Regression
  • Slide 31: Nonlinear Reg., Conditional Exp.
  • Slide 32: Markov Chain I
  • Slide 33: Markov Chain II
  • Slide 34: Continuous Probability I
  • Slide 35: Continuous Probability II
  • Slide 36: Continuous Probability II
  • Slide 37: Gaussian RV, CLT
  • Slide 38: Random Thoughts
  • Slide 39: Final Review (Probability)
Expand