CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lectures: M/Tu/W/Th 2-3:30 pm, 155 Dwinelle
Week 1 Overview
Propositional Logic, Proofs, Induction
- Note 0 : Review of Sets, Notation
- Note 1 : Propositional Logic
- Note 2 : Proofs
- Note 3 : Induction
- Discussion 01a
- Discussion 01b
- Discussion 01c
- Discussion 01d
- Homework 00 (TeX)
- Lecture 1
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 01a: Propositional Logic
- Discussion 01b: Proofs
- Discussion 01c: Induction
- Discussion 01d: Induction
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.
Lecture Slides
- Lecture 1: Introduction, Propositional Logic