# InfoCoBuild

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

 Introduction

 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

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