CS 70 - Discrete Mathematics and Probability Theory
CS 70: Discrete Mathematics and Probability Theory (Fall 2012, 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.
Lecture 01 - Instruction, Propositions & Quantifiers |
Lecture 02 - Quantifiers, Proofs |
Lecture 03 - Proofs |
Lecture 04 - Induction |
Lecture 05 - Induction: Three Forms of Induction, Strengthening the Induction Hypothesis |
Lecture 06 - The Stable Marriage Problem |
Lecture 07 - Modular Arithmetic |
Lecture 08 - Euclid's GCD Algorithm, Bijections |
Lecture 09 - Fermat's Little Theorem, RSA Cryptosystem |
Lecture 10 - Polynomials, Finite Fields |
Lecture 11 - Secret Sharing, Finite Fields, Erasure Codes |
Lecture 12 - Error Correcting Codes |
Lecture 13 |
Lecture 14 - Graphs and Induction |
Lecture 15 - Counting |
Lecture 16 - Probability |
Lecture 17 - Birthday Paradox, Monty Hall Paradox |
Lecture 18 |
Lecture 19 - Independence, Unions, Random Variables |
Lecture 20 - Expectation Variance |
Lecture 21 - Variance, Markov's Inequality, Chebyshev's Inequality |
Lecture 22 - Geometric, Poisson Distributions |
Lecture 23 - Continuous Probability |
Lecture 24 - Exponential Distribution, Gaussian Distribution, Kalman Filter |
Lecture 25 - Inference, Kalman Filter, Midterm |
Lecture 26 - Countable, Uncountable, Uncomputable |