CS70
Discrete Mathematics and Probability Theory
Summer 2016
Instructors: Alexandros Psomas, Grace Dinh, Fan Ye
Lecture: MTuWTh 2-3:30P, 245 LI KA SHING
Instructors: Alexandros Psomas, Grace Dinh, Fan Ye
Lecture: MTuWTh 2-3:30P, 245 LI KA SHING
Official Notes
There is no textbook for this class. Instead, there is a set of fairly comprehensive lecture notes. Notes posted well in advance of lecture may change closer to the date. So make sure you revisit the notes after lecture. Note 0 is background material that you should make sure you understand before the first lecture. Each note may be covered in one or more lectures.- Note 0: Review of Math Notation
- Note 1: Propositions and Quantifiers
- Note 2: Proofs
- Note 3: Induction
- Note 4: Graph Theory
- Note 5: Stable Marriage
- Note 6: Infinity and Countability
- Note 7: Counting
- Note 8: Self-Reference and Computability
- Note 9: Introduction to Discrete Probability
- Note 10: Conditional Probability
- Note 11: Two Killer Applications
- Note 12: Random Variables: Distribution and Expectation
- Note 13: Variance
- Note 14: Chebyshev's Inequality
- Note 15: Some Important Distributions
- Note 16: Continuous Probability
- Note 17: Chernoff Bounds
- Note 18: Markov Chains
- Note 19: How to Lie with Statistics
- Note 20: Modular Arithmetic
- Note 21: Bijections and RSA
- Note 22: Polynomials and Secret Sharing
- Note 23: Error Correcting Codes
- Note 24: The Chinese Remainder Theorem and Remote Coin Flipping
Extra Notes
Here are some additional notes on Chernoff Bounds by Prof. Sahai, from Fall 2014: Notes on Chernoff Bounds And here are some additional notes compiled by previous TAs:Weekly Resources
Week number | Dis A | Dis B | Dis C | Dis D | HW problem | HW Due Data | HW Sol |
---|---|---|---|---|---|---|---|
Week 0 | N/A | N/A | N/A | N/A | Homework 0 |
|
Solution |
Week 1 | 1A; Sol | 1B; Sol | 1C; Sol | 1D; Sol | Homework 1 |
|
Solution |
Week 2 | 2A; Sol | 2B; Sol | 2C; Sol | 2D; Sol | Homework 2 |
|
Solution |
Week 3 | N/A | 3B; Sol | 3C; Sol | N/A | Homework 3 |
|
Solution |
Week 4 | 4A; Sol | 4B; Sol | 4C; Sol | 4D; Sol | Homework 4 |
|
Solution |
Week 5 | 5A; Sol | 5B; Sol | 5C; Sol | 5D; Sol | Homework 5 |
|
Solution |
Week 6 | 6A; Sol | 6B; Sol | 6C; Sol | Homework 6 |
|
Solution | |
Week 7 | 7A; Sol | 7B; Sol | 7C; Sol | 7D; Sol | Homework 7 |
|
Solution |
Week 8 | 8A; Sol | N/A | N/A | N/A | No homework | N/A | N/A |