CS 70 - Discrete Mathematics and Probability Theory

CS 70: Discrete Mathematics and Probability Theory (Spring 2015, UC Berkeley). Instructor: Professor Umesh Vazirani. This course discusses the foundation for many algorithms, concepts, and techniques in the field of Electrical Engineering and Computer Science. Topics covered in this course include: Logic, infinity, and induction; applications include undecidability and stable marriage problem. Modular arithmetic and GCDs; applications include primality testing and cryptography. Polynomials; examples include error correcting codes and interpolation. Probability including sample spaces, independence, random variables, law of large numbers; examples include load balancing, existence arguments, Bayesian inference.


Lecture 01 - Introduction, Propositions and Quantifiers
Lecture 02 - Proofs
Lecture 03 - Induction
Lecture 04 - Induction (continued) and Recursion
Lecture 05 - Stable Marriage Problem
Lecture 06 - Graphs, Eulerian Tour
Lecture 07 - Graphs: Trees and Hypercubes
Lecture 08 - Modular Arithmetic
Lecture 09 - Bijections, RSA Cryptosystem
Lecture 10 - Fermat's Little Theorem and RSA, Polynomials
Lecture 11 - Polynomials, Secret Sharing, Erasure Codes
Lecture 12 - ECC (Error-Correcting Codes)
Lecture 13 - Infinity, Uncountability, Diagonalization
Lecture 14 - Self-reference, Quines and Godel
Lecture 15 - Probability: Counting
Lecture 16 - Probability: Sample Spaces, Events, Independence, Conditional Probability
Lecture 17 - Conditional Probability
Lecture 18 - Two Killer Applications: Hashing and Load Balancing
Lecture 19 - Random Variables and Expectation
Lecture 20 - Linearity of Expectation and Examples, Independence, Variance
Lecture 21 - Variance, Chebyshev Inequality
Lecture 22 - Some Important Distributions: Binomial, Geometric, and Poisson Distributions
Lecture 23 - Continuous Probability
Lecture 24 - Inference
Lecture 25 - Zipf's Law and Power Law Distributions
Lecture 26 - How to Lie with Statistics

CS 70: Discrete Mathematics and Probability Theory, Spring 2015
Instructor: Professor Umesh Vazirani. Lecture Notes. Exams. Homework Assignments with Solutions. Discussion Handouts with Solutions. Syllabus.