CS 70: Discrete Mathematics and Probability Theory (Spring 2015, UC Berkeley) | Computer Science

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.