CS70
Discrete Mathematics and Probability Theory
Summer 2016
Instructors: Alexandros Psomas, David Dinh, Fan Ye
Lecture: MTuWTh 23:30P, 245 LI KA SHING
Instructors: Alexandros Psomas, David Dinh, Fan Ye
Lecture: MTuWTh 23: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: SelfReference 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 