# Lecture 11
 - *consistent:* given more accurate predictions, the online algorithm should perform close to the optimal offline algorithm, and
 - *robust:* if the prediction is wrong, the online algorithm performance should be close to the online algorithm without predictions:

# Lecture 12
- *Uniform distribution:* All chances are equal: $\text{Pr}(X=k)=\frac{1}{|\text{codom}(X)}$
- *Geometric distribution:* Number of trials until the first success in a sequence of Bernoulli trials: $\text{Pr}(X=k)=(1-p)^{k-1}p$, $\mathbb{E}[X]=\frac{1}{p}$.

# Lecture 13

- *Yao’s Principle, informal:* The worst-case performance of the best
  randomized algorithm is equal to the average performance of the best
  deterministic algorithm on the worst distribution of the inputs or
- If $$\frac{a}{b}$$. In other words the average performance of the best deterministic algorithm is greater than $c$, then $$\frac{\mathcal{E}_{\text{Rand}}\left[\text{Rand}(I)\right]}{\text{Opt}(I)}\geq c$$
- *Coupon Collector’s Problem:* If each box of breakfast cereal contains a
  coupon, and there are $n$ different coupons, how many boxes do you need to buy
  in expectation to collect all $n$ coupon? Answer $nH_n$.