Midterm two Cheat Sheat

# 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
1. With replacement, order matters
1. Example: $2^n$ ways of flipping a {H, T} coin n times
2. Without replacement, order matters
1. Example: 52 cards, draw 5
2. 52 51 50 49 48
3. $\frac{n!}{(n-k)!}$
3. Without Replacement, Order doesn't matter
1. Example: 52 cards, Queen of Hearts, King of Spades, Jack of Diamonds, Ace of Clubs, 10 of diamonds
2. ${n \choose k} = \frac{n!}{(n-k)!k!}$
4. With replacement, Order doesn't matter:
1. Example: 3 types of veggies, pick 5 from an unlimited number
2. Think: Balls and Bins
3. Balls: number of servings we want to make (n balls)
4. Bins: different types of veggies we have (k bins)
5. ${n - 1 + k \choose n}$
1. ** Also equivalent to: $n-1+k \choose k-1$

page revision: 21, last edited: 12 Nov 2013 10:07