# Topics likely to be covered:

**Error Correcting Codes and Secret Sharing**

A polynomial $P(x)$ of degree at most $d$ can be uniquely identified by knowing it's value at $d+1$ points.

There is a unique polynomial of degree at most $d$ such that it hits all $d+1$ points.

Berlekamp and Welch: If the e1, e2 …. ek packets are corrupted so that the received points are r1, r2…rk we can define E(x) = (x-e1)(x-e2)…(x-ek) and Q(x) = P(x)*E(x). Then we use Q(i) = ri * E(i) to solve for Q(x) and E(x) whose quotient is P(x). Q is of degree n + k - 1 and E is degree k with the first coefficient equal to 1.

**Graphs**

Every graph that is connected except for vertices of degree 0 has an Eulerian Tour if every vertex has an even degree.

sum deg(v) = 2|E| where v exists in V

**Probability**

If A and B are independent it is true that $P(A\cap B) = P(A)P(B)$ and (if both $P(A) \neq 0$, $P(B) \neq 0$) also $P(A|B) = P(A)$.

As long as both A and B have nonzero probability is always true that $P(A\cap B) = P(A|B)P(B)= P(B|A)P(A)$

**Counting**

There are $n!$ ways to order $n$ objects.

Ways of Counting

- With or Without Replacement
- Order does or doesn't matter

- With replacement, order matters
- Example: $2^n$ ways of flipping a {H, T} coin n times

- Without replacement, order matters
- Example: 52 cards, draw 5
- 52 51 50 49 48
- $\frac{n!}{(n-k)!}$

- Without Replacement, Order doesn't matter
- Example: 52 cards, Queen of Hearts, King of Spades, Jack of Diamonds, Ace of Clubs, 10 of diamonds
- ${n \choose k} = \frac{n!}{(n-k)!k!}$

- With replacement, Order doesn't matter:
- Example: 3 types of veggies, pick 5 from an unlimited number
- Think: Balls and Bins
- Balls: number of servings we want to make (n balls)
- Bins: different types of veggies we have (k bins)
- ${n - 1 + k \choose n}$
- ** Also equivalent to: $n-1+k \choose k-1$