SYLLABUS

Counting, Probability, Random Variables

- Sum and product rules, inclusion-exclusion, product tree
- Pigeonhole principle
- Permutations & Combinations, binomial coefficients, binomial theorem
- Intro to prob.  Sample spaces, events, simple examples: coins, dice, program bugs, poker hands
- Conditional probability, Bayes rule, examples: false positive/false negative, spam detection
- Independence, random variables
- Expectation, bernoulli trials, binomial distribution
- Variance, tail bounds (Chebyshev inequality)
- Chernoff bounds
- Application: Entropy and data compression
- Continuous random variables; exponential and normal distributions, Poisson approximation

Applications, Central Limit Theorem, Statistics

- The Central Limit Theorem
- Lying with statistics
- Parameter estimation, confidence intervals, bias
- Monte-carlo simulation, polling, sampling
- Maximum likelihood estimation
- Bayesian estimation, Bayes classifier, machine learning

Polynomial Time and NP-completeness

- Polynomial-time algorithms:  Discussion, explanation, simple examples
- Divide-and-conquer
- Dynamic programming (least squares, edit distance)
- Search problems vs. decision problems, the class NP
- NP-completeness, SAT
- Reductions
- Practical implications of NP-completeness