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$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License