CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lectures: M/W/F 1-2 p.m., 150 Wheeler
Professor Kannan Ramchandran
kannanr (at) eecs.berkeley (dot) edu
Office Hours: W 2-3 p.m., 269 Cory
Professor Satish Rao
satishr (at) cs.berkeley (dot) edu
Office Hours: W 3-4 p.m., 687 Soda. Also after class at Wheeler: I always keep 30 minutes available.
Week 0 Overview
Propositional Logic, Proofs
Week 1 Overview
Induction, Stable Marriage
Week 2 Overview
Graph Theory
Week 3 Overview
Modular Arithmetic
- Note 6 : Modular Arithmetic
- Discussion 03a (solution)
- Discussion 03b (solution)
- Homework 03 (TeX) (solution)
- Lecture 8 (full) (6up)
- Lecture 9 (full) (6up)
- Lecture 10 (full) (6up)
Week 4 Overview
Midterm 1, RSA
Week 5 Overview
Polynomials, Error-Correcting Codes
Week 6 Overview
Countability, Computability, Counting
Week 7 Overview
Counting, Probability Spaces, Conditional Probability
Week 8 Overview
Bayes Rule, Random Variables
Week 9 Overview
Midterm 2, Expectation, Distributions
Notes
There is no textbook for this class. Instead, there is a set of fairly comprehensive lecture notes. Make sure you revisit the notes after lecture. Each note may be covered in one or more lectures. See Syllabus for more information.
- Note 0: Review of Sets, Notation (PDF)
- Note 1: Propositional Logic (PDF)
- Note 2: Proofs (PDF)
- Note 3: Induction (PDF)
- Note 4: Stable Marriage (PDF)
- Note 5: Graph Theory (PDF)
- Note 6: Modular Arithmetic (PDF)
- Note 7: Bijections and RSA (PDF)
- Note 8: Polynomials (PDF)
- Note 9: Error Correcting Codes (PDF)
- Note 10: Infinity and Uncountability (PDF)
- Note 11: Self-Reference and Uncomputability (PDF)
- Note 12: Counting (PDF)
- Note 13: Introduction to Discrete Probability (PDF)
- Note 14: Conditional Probability (PDF)
- Note 15: Two Killer Applications (PDF)
- Note 16: Random Variables: Distribution and Expectation (PDF)
- Note 17: Variance (PDF)
- Note 18: Chebyshev's Inequality (PDF)
- Note 19: Some Important Distributions (PDF)
- Note 20: Continuous Probability (PDF)
- Note 24: Markov Chains (PDF)
- Note 25a: Review of Probability (PDF)
- Note 25b: Probability: An Overview (PDF)
- Note 26: Estimation (PDF)
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 00b: Propositional Logic (solution)
- Discussion 01a: Proofs, Induction (solution)
- Discussion 01b: Induction, Well-Ordering Principle (solution)
- Discussion 02a: Stable Marriage (solution)
- Discussion 02b: Graph Theory I (solution)
- Discussion 03a: Graph Theory II (solution)
- Discussion 03b: Modular Arithmetic I (solution)
- Discussion 04b: Modular Arithmetic II (solution)
- Discussion 05a: RSA (solution)
- Discussion 05b: Polynomials (solution)
- Discussion 06a: Error-Correcting Codes (solution)
- Discussion 06b: Countability, Computability (solution)
- Discussion 07a: Counting, Combinatorial Proofs (solution)
- Discussion 07b: Probability Spaces (solution)
- Discussion 08a: Conditional Probability, Birthday Paradox, Bayes Rule (solution)
- Discussion 08b: Bayes Rule, Independence, Binomial Distribution (solution)
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. 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) (solution)
- Homework 01: Propositional Logic, Proofs (TeX) (solution)
- Homework 02: Induction, Stable Marriage (TeX) (solution)
- Homework 03: Graphs (TeX) (solution)
- Homework 04: Modular Arithmetic (TeX) (solution)
- Homework 05: RSA, Polynomials (TeX) (solution)
- Homework 06: Polynomials, Error-Correcting Codes (TeX) (solution)
- Homework 07: Countability, Computability, Counting (TeX) (solution)
- Homework 08: Combinatorial Proofs, Probability (TeX) (solution)
- Homework 09: Random Variables, Distributions (TeX)
Lecture Slides
- Lecture 1 (full) (6up): Introduction, Propositional Logic
- Lecture 2 (full) (6up): Propositional Logic, Proofs
- Lecture 3 (full) (6up): Proofs. Induction.
- Lecture 4 (full) (6up): Induction
- Lecture 5 (full) (6up): Stable Marriage
- Lecture 6 (full) (6up): Graphs
- Lecture 7 (full) (6up): Trees, Complete, Planar
- Lecture 8 (full) (6up): Planar, Mod. Arith. (Intro)
- Lecture 9 (full) (6up): GCD: Euclid
- Lecture 10 (full) (6up): EGCD; Midterm Review
- Lecture 11 (full) (6up): CRT: RSA (start)
- Lecture 12 (full) (6up): RSA: Signature Schemes
- Lecture 13 (full) (6up): Polynomials: Secret Sharing, Erasure Codes
- Lecture 14 (full) (6up): Erasure Codes, Error Correction
- Lecture 15 (full) (6up): Erasure Codes, Countability
- Lecture 16 (full) (6up): Countability/Undecidability
- Lecture 17 (full) (6up): Undecidability/Counting
- Lecture 18 (full) (6up): Counting
- Lecture 19 (full) (6up): Introduction to Probability
- Lecture 20 (full) (6up): Conditional Probability
- Lecture 21 (full) (6up): Conditional Probability, Bayes Rule (Draft)
- Lecture 22 (full) (6up): Random Variables, Distributions
- Lecture 23 (full) (6up): Review (Draft)
- Lecture 24 (full) (6up): Expectation (Draft)
- Lecture 25 (full) (6up): Important Distributions (Draft)