# 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.