infocobuild

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.

Introduction


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

References
CS 70: Discrete Mathematics and Probability Theory, Fall 2012
Instructor: Professor Umesh Vazirani. Lecture Notes. Section Materials. Exam Solution. Homework Solutions. Syllabus.