cs70.txt

= before midterm 1 =

conjunction: P and Q; disjunction: P or Q; negation: not P; truth table
implication: P => Q logically equivalent to (not P) or Q; contrapositive: not Q => not P; converse: Q => P;

Direct proof, proof by contraposition, proof by contradiction, proof by cases, induction, strong induction, well ordering principle, 
Induction: Base case + Induction hypothesis (for some k >= 1, assume ...) + Induction step (by the induction hypothesis)
Thus, assuming the statement holds for some value k, we have shown it is also holds for the value k + 1. This completes the induction step and hence the proof by induction.

RSA: Pick N = pq (p, q primes), e such that gcd(e, (p-1)(q-1)) = 1. pubkey: (N, e); private key: d. Property: (x^e)^d = 1 mod N
Fermat's Little Theorem: for any prime p and integer a in {1, 2, . . . , p ‚àí 1}, we have a^(p‚àí1) = 1 mod p.
By Fermat's Little Theorem, k^m = k^(m mod (p-1)) mod p
nonexistence of stable match of roommates
[A | B C D], [B | C A D], [C | A B D], [D | - - -]
{(A, B), (C, D)} => {(A, D), (B, C)} => {(A, B), (C, D)} => ...

Every Morning: Each man goes to the first woman on his list not yet crossed off and proposes to her.
Every Afternoon: Each woman says ``maybe'' to the man she likes best among the proposals (she now has him on a string) and ``never'' to all the rest.
Every Evening: Each of the rejected suitors crosses off the woman from his list.

Termination Lemma: guaranteed to terminate in n^2 days.
Improvement Lemma: If W has M on a string on the kth day, then on every subsequent day she has someone on a string whom she likes at least as much as M.
Lemma: The algorithm terminates with a pairing.
Theorem: The pairing produced by the algorithm is always stable.
    Proof technique: Suppose (M, W), (M*, W*), M prefer W* over W, prove that W* prefer M* over M.
Def: The optimal woman for a man is the highest woman on his list whom he is paired with in any stable pairing.
Def: Male optimal pairing is a stable pairing such that each man is paired with his optimal woman.
Theorem: The pairing output by the traditional propose & reject algorithm is male optimal.
    Proof technique: Assume not & let k be 1st day someone rejected by optiomal. M rejected by W* in favor of M*. Exists stable T : (M, W*), (M*, W'). Prove that (M*, W*) rogue.
Theorem: If a pairing is male optimal, then it is also female pessimal. (prove by contradiction)

Lagrange interpolation: delta_i (x) = prod_{j!=i} (x-xj) / prod_{j!=i} (xi-xj)
Secret sharing: at least k people => pick random polynomial with deg k-1 s.t. P(0) = secret. Give P(1) to 1st, ..., P(n) to nth. 
Erasure errors: n packets, at most k packets lost => polynomial deg n-1. send n+k packets. must have prime q>=n+k
General errors: n packets, at most k packets corrupted => polynomial deg n-1. send n+2k packets. must have q>=n+2k. polynomial 
Error locator polynomial E(x) = (x-e1)…(x-ek); P(i)E(i)=R(i)E(i). Let P(x)E(x)=Q(x). Solve Q(x)=R(x)E(x) deg n+k-1 + deg k. But leading coefficient of E is 1.
Q(x) = a_{n+k-1}x^{n+k-1} + … + a0; E(x) = x^k + b_{k-1}x^{k-1} + … + b0

gcd = (x, y) -> y == 0 ? x : gcd(y, x mod y) (assume that x >= y >= 0 and x > 0)
def extended-gcd (x, y):
    return (x, 1, 0) if y == 0
    (d, a, b) = extended-gcd (y, x mod y)
    return (d, b, (a - int(x / y) * b))

= before midterm 2 =

Graphs are allowed to have self-loops, but assume they don't.

path: a sequence of neighboring edges. A path between v1 and vn: (v1, v2), (v2, v3), ..., (vn-1, vn)

simple path: no repeated vertices.

cycle: a path that begins and ends at the same vertex.

connected graph: exists path between any two distinct vertices.

degree: (undirected graph) degree(v) = |{u in V: (v, u) in E}|. (directed graph) in-degree, out-degree

isolated vertex: deg = 0

multigraph: multiple edges between the same pair of vertices

Eulerian path / Eulerian walks: a path in a graph that uses each edge exactly once (not simple)

Eulerian tour / Eulerian cycle: an Eulerian path whose starting point is the same as its ending point

Euler's Theorem: An undirected graph G = (V, E ) has an Eulerian tour if and only if the graph is connected (except possibly for isolated vertices) and every vertex has even degree. (for directed graph: for every vertex v, in-degree = out-degree)
    Proof technique: start from any vertex u, go until stuck (must stuck at u by lemma: walk u->v, only u and v can have odd degree). Find an edge not covered with one vertex on the current walk, splice in.

de Bruijn sequence: a 2^n-bit circular sequence such that every string of length n occurs as a contiguous substring of the sequence exactly once.

de Bruijn graph: V = {0, 1}^(n-1), E = for each a1a2...an-1, (a1a2...an-1, a2a3...a{n-1}0), (a1a2...an-1, a2a3...a{n-1}1), (0a1a2...an-2, a1a2...a{n-1}), (1a1a2...an-2, a1a2...a{n-1})

n-dimensional hypercube graph: undirected, V = {0,1}^n, E = (x,y) iff x,y differ in one place. 2nd def: n-dim = 2 * (n-1)-dim + edges between corresponding vertices, i.e. x in 0-cube and x in 1-cube
    |E| = n2^(n-1)
    Let E_{S, V-S} denote the set of edges connecting vertices in S to vertices in V-S. Then |E_{S, V-S}| >= min(|S|, |V-S|) (prove by induction on n, consider S0, S1 both <= 2^(n-1)/2; or S0 > 2^(n-1)/2)
    has a Hamiltonian cycle => Gray code
        proof: induction on n. Select 0v adjacent to 0^n. 0^n --(hamiltonian path)-> 0v -> 1v --(h path)-> 1^n -> 0^n

Hamiltonian path / cycle: a path / cycle that goes through every vertex exactly once.

first rule of counting: object made by succession of k choices. n1 ways of 1th choice, ..., nk ways of kth choices => n1 * n2 * .. * nk

first rule of counting: object made by succession of k choices. order doesn't matter. First count as order matters, then divide #ordered per unordererd.

place k balls into n bins: Represent each of the balls by a 0 and the separations between boxes by 1’ => k * 0 + (n-1) * 1 => n+k-1 choose k

n choose k+1 = (n-1 choose k) + (n-2 choose k) + ... + (k choose k)

probability space is a sample space Omega, together with a probability Pr[w] for each sample point w, such that 0 <= Pr[w] <= 1 for all w in Omega, and sum Pr = 1. outcome - sample point

event: subset of sample space. Pr[A] = sum_{w in A} Pr[w]

Monty Hall: (i, j, k). i: location of prize; j: initial door chosen by the contestant; j: door opened

Independence: A independent B if Pr[A cap B] = Pr[A] * Pr[B]. A1, ..., An mutually independent if for every subset I in {1, ..., n}, Pr[Cap{i in I} Ai] = Mult{i in I} Pr[Ai]. Pairwise independence (every pair independent)

Bayes' Rule: Pr[A|B] = Pr[B|A]Pr[A] / Pr[B]

Total Probability Rule: Pr[B] = Pr[B|A]Pr[A] + Pr[B|not A] (1 - Pr[A])

Product Rule: Pr[Cap{i=1 to n} Ai] = Pr[A1] * Pr[A2|A1] * Pr[A3|A1 cap A2] * ... * Pr[An|Cap{i=1 to n-1} Ai]

Principle of Inclusion/Exclusion: Pr[union] = ....

Union bound: Pr[union] <= sum of Pr

Hash table: n locations. A = event: insert m keys with no collisions, assuming uniformly distributed hash function.
    Pr[A] = (1 - 1/n) * (1 - 2/n) * ... * (1 - (m-1)/n). Take ln: ln(1-x) ~ -x. ln(Pr[A]) ~ -m^2/2n => Pr[A] ~ e^(-m^2/2n)
    union bound: Ai: pair i has collision. Pr[bar A] <= sum Pr[Ai] = m(m-1)/2n

a random variable X on a sample space Omega is a function that assigns to each sample point w in Omega a real number X(w)

Pr[X=a] = Pr[{w in Omega: X(w) = a}]

distribution: collection of values {(a, Pr[X=a]): a in A}, where A is the set of all possible values taken by X
    the collection of events form a partition of the sample space

binomial distribution: Pr[X=i] = (n choose i)p^i(1-p)^(n-i). X ~ Bin(n, p). E[X] = np

error correction: encode n packets into n+k packets s.t. the recipient can reconstruct the original n packets from any n packets received. packets lost with prob p. X (packets received) ~ Bin(n+k, 1-p)

expectation / mean / average of r.v.: definition: E(X) = sum_{a in A} a * Pr[X=a]
    rewritten: E(X) = sum_{w in Omega} X(w) * Pr(w)

linearity of expectation: for any two random variables X, Y on the same probability space, for any constant c, E(X+Y) = E(X) + E(Y); E(cX) = cE(X)

indicator random variable: 0/1-valued random variable. E(Xi) = 0 * Pr[Xi=0] + 1 * Pr[Xi=1] = Pr[Xi=1]

expected number of fixed points in a random permutation of n items is always 1

throw m balls into n bins. Y = number of empty bins. E[Y] = n(1-1/n)^m

geometric distribution: X ~ Geom(p). Pr[X=i] = (1-p)^(i-1)p. E[X] = 1/p
    biased coin, Pr[head] = p. tossed repeatedly until first head.

Theorem: Let X be a random variable that takes on only non-negative integer values. Then E[X] = sum_{i=1}^infinity Pr[X>=i]. Pr[X>=i] = (1-p)^(i-1)

collect set of n different cards. X = boxes need to buy to collect at least one copy of each card. Xi = #boxes buy while trying to get the ith new card. 
    E(Xi) = n / (n - i + 1) => E(X) = n sum_{i=1}^n 1/i ~ n (ln n + lambda)
    lambda = 0.5772... Euler constant

Poisson distribution: Pr[X=i] = lambda^i/i! * e^(-lambda), Poisson distribution with parameter lambda. X ~ Poiss(lambda). E[X] = lambda
    limit of the numbers of balls in bin 1 when n balls are thrown into n/lambda bins

= before final =

E(X^2) = E((X1+...+Xn)^2) = sum_i E(Xi^2) + sum_{i!=j} E(XiXj)
variance: Var(X) = E((X - E(X)))^2 (definition) = E(X^2) - (E(X))^2
standard deviation: sigma(X) = sqrt(Var(X))

random walk: E(X^2) = n, Var(X) = n
binomial distribution: E(X^2) = n^2p^2 + np(1-p), Var = np(1-p)
Poisson distribution: E(X^2) = lambda * (lambda + 1), Var(X) = lambda
Number of fixed points in a random permutation: E(X^2) = 2, Var(X) = 1

Markov's inequality: For a nonnegative r.v. X with E(X) = miu, and any alpha > 0, Pr[X >= alpha] <= E(X) / alpha
  proof technique: note sum_a a*Pr[X=a] >= sum_{a >= alpha} a*Pr[X=a]
Chebyshev's inequality: For a random variable X with expectation E(X) = miu, and for any alpha > 0, Pr[|X-miu| >= alpha] <= Var(X) / alpha^2
  proof technique: define r.v. Y := (X-miu)^2. Pr[|X-miu| >= alpha] = Pr[Y >= alpha^2]. Apply Markov's inequality
  corollary: r.v. X with E(X) = miu, sigma = sqrt(Var(X)), Pr[|X-miu| >= beta*sigma] <= 1 / beta^2

i.i.d: independent, identically distributed

for any r.v. X and constant c, Var(cX) = c^2Var(X)

estimate a proportion p by taking a small sample
  An = Sn / n = (X1 + ... + Xn) / n
  Var(An) = Var(Xi) / n = p(1-p) / n
  Pr[|An-p| >= epsilon*p] <= Var(An) / (epsilon*p)^2 <= delta
    => n >= (sigma^2 / miu^2) * 1 / (epsilon^2 * delta)
    => n >= (1-p)/p*1/(epsilon^2 * delta)

Law of Large Numbers: X1, ..., Xn i.i.d. r.v. with common E(Xi) = miu. Define An := 1/n sum_i Xi. Then for any alpha > 0, we have Pr[|An - miu| >= alpha] -> 0 as n -> oo

joint distribution: collection of values {(a, b, Pr[X=a, Y=b]): (a, b) in A cross B}
  E(f(X,Y)) = sum_c c*Pr[f(X,Y)=c] = sum_a sum_b f(a,b)*Pr[X=a,Y=b]
  Pr[X=a] = sum_{b in B} Pr[X=a, Y=b]
  Pr[Y=b] = sum_{a in A} Pr[X=a, Y=b]

independent r.v.'s: X, Y independent if the events X=a and Y=b are independent for all values a,b. Or Pr[X=a,Y=b] = Pr[X=a]Pr[Y=b] forall a,b
  X,Y independent => E(XY) = E(X)E(Y)
  X,Y independent => Var(X+Y) = Var(X) + Var(Y)

covariance of X, Y: E(XY) - E(X)E(Y)

conditional distribution: X given Y=b is collection of values {(a, Pr[X=a|Y=b]): a in A}

conditional expectation: E(X|Y=b) = sum_{a in A} a * Pr[X=a|Y=b]

total expectation law: E(X) = sum_{b in B} Pr[Y=b] * E(X|Y=b)

{(i, Pr[X=i]): i = 1, ..., n}: prior distribution of the hidden X.
{(i, Pr[X=i|Y1=H]): i = 1, ..., n}: posterior distribution of X given the observation.

Pr[Y2=H|Y1=H] = sum_{i=1}^n Pr[X=i|Y1=H] * Pr[Y2=H|X=i, Y1=H]

conditional independence: A and B are said to be conditionally independent given C if Pr[A, B|C] = Pr[A|C] * Pr[B|C]

MAP (maximum a posteriori) rule: guess the value a* for which the conditional probability of X=a* given the observations is the largest

error probability analysis:
  Pr[E] = Pr[sum_i Z_i > n/2] = sum_{k=ceil(n/2)}^n {n choose k} p^k(1-p)^(n-k)
        = Pr[S > n/2] < Pr[|S-np|>n(1/2-p)] <= Var(S)/(n^2(1/2-p)^2) = p(1-p)/(1/2-p)^2 * (1/n)

probability density function: a function f:R->R s.t. Pr[a<=X<=b] = int_a^b f(x)dx for all a <= b
  condition: int_-oo^oo f(x) dx = 1

X discrete, Y = cX => distribution of Y: Pr[X=a] = Pr[Y=a/c]
X continuous, Y = cX => pdf of Y: f_Y(x) = 1/c f_X(x/c)

expectation: E(X) = int_-oo^oo xf(x) dx

variance: Var(X) = E((X - E(X))^2 = int_-oo^oo x^2f(x) dx - (int_-oo^oo xf(x) dx)^2

joint density: a function f:R^2->R s.t. Pr[a<=X<=b, c<=Y<=d] = int_c^d int_a^b f(x,y) dxdy for all a<=b, c<=d

independence for continuous r.v.'s: events a<=X<=b and c<=Y<=d are independent for all a,b,c,d. or f(x,y) = f1(x)f2(y)

exponential distribution: f(x) = lambda*e^(-lambda*x) if x>=0 else 0 (lambda > 0) (with parameter lambda)
  E(X) = 1/lambda, E(X^2) = 2/lambda^2, Var(X) = 1/lambda^2
  Pr[X>t] = int_t^oo lambda*e^(-lambda*x) dx = e^(-lambda*t)
  memoryless property: exponential distribution & geometric distribution
    Pr[X>s+t | X>t] = Pr[X>s]  (s > 0, t > 0)
  X1 exp with param l_1, X2 exp with param l_2 => Y = min{X1, X2} exp with param l_1+l_2

Normal distribution: X ~ N(miu, sigma^2). f(x) = 1/sqrt(2*pi*sigma^2) * e^(-(x-miu)^2 / (2*sigma^2)) (sigma > 0)
  when miu=0 and sigma=1, standard normal distribution
  in general, Y = (X-miu) / sigma has the standard normal distribution

Central Limit Theorem: Let X1,...,Xn be i.i.d.r.v. with common expectation miu=E(Xi) and variance sigma^2=Var(Xi) (both assumed to be <oo). Define A'n = (sum_i Xi-n*miu) / (sigma*sqrt(n)). Then as n->oo, the distribution of A'n approaches the standard normal distribution in the sense that, for any real alpha,
  Pr[A'n<=alpha] -> 1/sqrt(2pi) int_-oo^alpha e^(-x^2/2) dx as n->oo

bijection from N to Z: f(x) = x/2 if x is even else -(x+1)/2

Cantor-Bernstein theorem: if |A| <= |B| and |B| <= |A| then |A| = |B|

injection from N to Q: N -> Z*Z -> Q. The latter by mapping rational number to 2D points, and go by spiral

finite binary strings countable (prove by listing strings in increasing order of length, and then in lexicographic order)

set of all polynomials with natural number coefficients countable

[0, 1] uncountable. prove by diagonalization, add 2 to each digit

cantor set: repeatedly remove 1/3 ~ 2/3 of interval. uncountable set of measure 0
  represent each number as ternary strings. C = {x in [0,1]: x has ternary representation of only 0's and 2's}
  divide each ternary string by 2 -> onto [0, 1]

S countably infinite => |P(S)| > |S|

halting problem: Turing(P): if TestHalt(P, P) = "yes" then loop forever; else halt. Turing(Turing) contradiction