4. Planar Graphs

• Planarity
  • Plane Graph
  • Euler’s theorem: $n-m+f=2$
    • Use it to show certain graphs are not planar
  • A plane graph with $n\ge 3$ vertices has at most $3n-6$ edges, which is achieved by plane triangulation
  • Planar Graph: If it can be embedded in the plane: if it is isomorphic to a plane graph.
• Minors and Topological Minors
  • Definitions of Minors:
    1. Remove vertices, then remove edges, then contract edges arbitrarily
    2. In the exact order: remove vertices, remove edges, contract edges
    3. $G$ contains $H$ as a minor if letting $v_1…v_h$ be the vertices of $H$, there are disjoint connected subgraphs $X_1…X_h$ such that $(v_i, v_j)\in E(H)$ means that $X_i,X_j$ in $G$.
  • Equivalence Proof:
    • 1 $\Rightarrow$ 2 is trivially true
    • 2 $\Rightarrow$ 3: Remove all vertices not in $H$, all edges not in $H$, and contract each $X_i$ to $v_i$.
    • 3 $\Rightarrow$ 1: For any edge contraction on $(x,y)$, we ‘uncontract’ by union the vertex sets $x, y$ are in. $v_i, v_j$ edge is an $X_i, X_j$ edge because edges are never deleted, so this edge is present in $G$ too.
  • If $\Delta(H)\le 3$, and $H$ is a minor of $G$, then $H$ is a topological minor of $G$
    • Proof: Use definition 3 above. Get a tree $T_i$ on $X_i$.
  • Every topological minor is also a minor
• Kuratowski’s and Wagner’s Theorem
  • Lemma 4.4.2: A graph $G$ contains $K^5$ or $K_{3,3}$ as minors if and only if it contains them as topological minors
    • Proof: Suffice to show that a $K^5$ minor leads to $K^5$ topological minor, or $ K{3,3} $ minor. If all trees in $ IK^5 $ are $ K{1,4} $ then we have a $K^5$ topological minor. Otherwise, there are two vertices of degree $3$, and the 6 vertices form a $K_{3,3}$ minor.
  • Lemma 4.4.3 Every 3-connected graph $G$ without $K^5$ or $K_{3,3}$ minor is planar
    • Proof: Prove by induction on $|G|$. Base case is $K^4$, true. Consider $G$ contract edge $xy$. The remaining graph is planar by induction, and 3-connected by lemma 3.2.4. If we remove vxy, it is 2-connected. So the boundary is a cycle. Denote Pi to be the path from $xi$ to $x{i+1}$. If we can show that all of $y$ neighbors are in a certain segment path Pi, then we can put $y$ in and still have a planar graph. Case 1, y has a neighbor in $P_i$ and one outside, then $y’, y’’$ are separated by two of x neighbors, there is a k3,3. Case 2, y’s neighbors are a subset of x neighbors. Thus, if y has 2 neighbors, this is case 1. If y has more than 2, then there is a TK5. Thus, it must be planar.
• Crossing Numbers:

5. Coloring

• Four color theorem, Kempe Chain:
• Greedy Algorithm:
  • Can be arbitrarily good or bad. There exists a vertex ordering such that the greedy gives the best chromatic number. There exists bipartite graph can be colored with an arbitrarily large number of colors using the greedy algorithm (not connecting vi and ui).
• Coloring Number $col(G)$:
  • The min k such that there exists an ordering, each vi has back-degree $< k$.
  • $col(G)\le max \delta(H) + 1$ if we use max to min ordering
  • $col(G)\ge col(H) \ge \delta(H) + 1$ easily
  • Thus, 5.2.2, $\chi(G)\le col(G) = max \delta(H)+1$
• Planar graphs are 6-colorable, 5-colorable: Proof by Kempe Chain
• Brook’s theorem:
  • If $G$ is neither complete nor an odd cycle, then $\chi(G)\le \Delta(G)$
  • Proof is by induction
• Lower bounds and Upper bounds of $\chi(G)$:
  • Lower:
    • $\omega(G)$. Obvious.
    • $\frac{n}{\alpha}$. Obvious, each color has at most $\alpha$ vertices
  • Upper:
    • $\Delta(G)+1$: Greedy algorithm
    • $n-\alpha +1$
    • $\Delta(G)$ for not complete or odd cycle graphs. Brook’s Theorem.
• Edge coloring $\chi’(G)$:
  • Konig Theorem: Every bipartite graph $G$ satisfies $\chi’(G)=\Delta(G)$.
• Vizing’s Theorem:
  • $\Delta(G)\le \chi’(G)\le \Delta(G)+1$
• List coloring $ch(G)$:
  • $ch(G)\ge \chi(G)$
  • Examples where $ch(G)>>\chi(G)$. hw7 q5. We show that there are graphs with $\chi(G)=2$ and $ch(G)=k$. We first show that there is a graph with $ch(G) \ge k$. Then we show that $ch(G-v)$ is at least $ch(G)-1$. Thus we can remove one vertex at a time to get $ch(G)=k$.
• Perfect Graphs:
  • Perfect elimination ordering:
    • For all $v_i$, its neighbors that come before it form a clique.
  • Proof that PEO graph is perfect
    • put max-clique vertex the end
  • Chordal Graph:
    • PEO graphs are chordal
  • Weak and Strong Perfect Graphs:
    • cliques, bipartite, and complements
    • A bipartite graph’s complement is perfect
    • Proof: Let $G$ be bipartite, then $\chi(\bar G) = M + n - 2M = n - M$. This is because $G$ has only cliques of 1, 2. This is the minimum number of cliques in $G$. In a bipartite graph, $M = n - \alpha$.

7 Extremal Graph Theory

• $R(H_1, H_2, … H_k)$ is the minimum $N$ such that every k coloring of the edges of $k^N$ yields some $i\in [k]$ for which $H_i$ is a subgraph of the ith color.
• SCHUR $S(k)$ is the largest $N$ such that $[N]$ can be partitioned into k sum free sets.
• Van Der Waerden is the least $N$ such that partitioning $[n]$ into R sets must yield.

Introduction

What Operating Systems Do

• A computer system can be divided into: hardware, operating system, application programs, users
• An operating system performs no useful function by itself, but provides an environment within which other programs can do useful work.

  Computer-system Organization

• Bootstrap program in ROM
• interrupt vector is an array of pointers to interrupt routines.
• I/O and storage

  Computer-system Architechture

• Multicore systems are multiprocessor, not all multiprocessor are multicore
• Blade servers : each processor boots independently and runs its own OS.
• Clustered System: Individual systems are joined via LAN to provide high availability (service will continue even one fails)

  Operating-system Structure

• Multiprogramming: Run multiple programs to increase the utilization of the CPU.
• Time Sharing: is a logical extension of multiprogramming that CPU executes multiple jobs by switching fast.
• To ensure reasonable response time, use swapping or virtual memory.

  Operating-system Operations

• A trap is a software-generated interrupt caused either by an error or request
• Use a mode bit to indicate in user mode or kernel mode to avoid user programs to crash OS.
• A Timer is used to detect possible infinite loops in user programs.

  Process Management

  -

List Processing

Lisp List

• List definition: '(a, b, c, d, ...)
• lists can be programs AND data
• Atom: indivisible element
• Atoms contain: numbers, symbols, …

  Run a Program

• ' tells List to do nothing with the list, otherwise, use the first element in the list as the function
• Use C-x C-e to evaluate a lisp expression in emacs

  Generate an Error Message

• Evaluate (a, b, c, d) will generate an error, type q to quit

  Functions and Arguments

• concat number-to-string

  The message function

• (message "This is a message")
• (message "The current buffer is %s" (buffer-name))

  Setting the Value of a Variable

• Using set: (set 'flowers '(rose violet daisy buttercup))
• Using setq: (setq flowers '(rose violet daisy buttercup))

  Practicing Evaluation

• To view documentation: (info "(elisp)Files")
• Each keystroke calls the self-insert-command, an interactive function
• (buffer-size) (point)

  How to Write Function Definitions

  The defun Macro

• A typical list function:

1
2
3
4

(defun function_name (args)
"documentation"
(interactive argument-passing-info) ; optional
body...)

• interactive: (interactive "p") uses prefix
• let:

1
2
3
4

(let ((var_name, var_value),
      (var_name, var_value)...)
      body...
)

• if:

1
2
3

(if (> 5 4)
(message "5 is greater than 4")
(message "otherwise"))

-

Auto-compelete and Yasnippet

gcc -xc++ -E -v -

iedit mode

flymake

Deductive System

A Deductive System consists of

• One or more initial objects
• One or more deduction rules

Propositional Logic

doesn’t have quantifiers, or “First Order Logic”

• Propositional Variables: basic statements that can be either true or false, like $p, w, r, x_1, x_2, x_3$
• Connectives:
  • Not $\neg$
  • And $\wedge$
  • Or $\vee$
  • Implies $\rightarrow$
  • If and Only if $\leftrightarrow$

formula: Connectives and P.V.
well-formed formula:

• Initial: Any variable
• Deduction Rules: From $A$, can obtain $\neg A$. From $A, B$, can obtain $A\vee B$, $A\wedge B$, $A\rightarrow B$, $A\leftrightarrow B$.

A formula is a binary tree in which:

• 2-child nodes are labeled by binary ops
• 1-child nodes are labeled by unary ops
• 0-child nodes are labeled by variables

Truth Assignment V: setting of true and false for each variable
Given a formula $S$, its truth value $V[S]$ can be defined by structural induction

Satisfiability:

• $V$ satisfies $S$: $V[S] = T$
• $S$ is satisfiable: $\exists V$ such that $V[S] = T$
• $S$ is unsatisfiable: $\forall V, V[S] = F$
• $S$ is tautology: $\forall V, V[S] = T$

Equivalent: Formulas $R$ and $S$ are equivalent, $R \equiv S$ if $\forall V, V[R] = V[S]$.

Entailment: Formulas $A_1, …, A_m$ entail formula $S$, written $A_1, …, A_m \models S$ if every truth assignment which makes $A_i$ true makes $S$ true.

Truth table: It represents a Boolean function, $f: {0, 1}^n \rightarrow {0, 1}$.

• There are $2^{2^n}$ truth tables on n variables.
• Every truth table can be computed by some formula, only using $\neg, \vee, \wedge$

Circuits

• In circuits, nodes (gates) may have fan-out > 1.
• Formulas are trees: all nodes have fan-out 1.
• Circuits can reuse already-computed pieces. Formulas cannot; everything must be “rebuilt”.
• Deduction viewpoint: The circuit is the deduction. The formula is the last line.

Formalization of Proof

First Order Logic = Prop. Logic + {$\forall$, $\exists$, $=$, “constants”, “relations”, “functions”}
Variables are now objects.
Vocabulary is a collection of constant-names, function-names, relation-names.
Interpretation

• Specifies the universe
• Maps constant-name to object
• Maps relation-name to actual relation
• Maps function-name to actual function
  Satisfiability/Tautology: Similar to that in first order logic.

Finite Automata

Alphabet: A nonempty finite set $\Sigma$ of symbols, $\Sigma = {0, 1}$ usually.
String: A finite sequence of 0 or more symbols.

• The length-0 string is $\epsilon$
• $\Sigma^n$ means all strings with length n.
• $\Sigma^{*}$ means all strings over $\Sigma$

Language: A collection of strings. A subset of $\Sigma^{*}$.

Thus, we can think of a decision problem as a function:
$f: \Sigma^{*} \rightarrow {NO, YES}$
Decision problem is finding a language L such that f(element in L) is true

DFA: $L(M) = x\in \Sigma^{*}: M \text{accepts } x$.

A deterministic finite automaton is a 5-tuple:

• $Q$ is a nonempty finite set of states
• $\Sigma$ is an alphabet
• $\delta: Q * \Sigma \rightarrow Q$ is the transition function
• $q_0\in Q$ is the start state
• $F\subset Q$ is the set of accepting states

Accept
Let $w = w_1w_2w_3…w_n$
We say that M accepts string w if there exists states $r_0r_1…r_n\in Q$ such that

• $r_0 = q_0$
• $\delta(r_{t-1}, w_t) = r_t$ for all $t$
• $r_n\in F$.
  Otherwise, we say $M$ rejects $w$.
  The sequence $r_1r_2…r_n$ is called the computation trace.

Regular Languages
A language is regular if there is a DFA that decides it

Proving a language is not regular

1. Assume for contradiction there is a DFA M which decides language L
2. Argue there are two strings x, y which reach the same state in M.
3. Show there is a string z such that $xz\in L$ and $yz\notin L$.
   Example: $a^nb^n$

• $L_1\cup L_2$ is regular if $L_1$ and $L_2$ are.(Union Theorem)
• $L_1\dot L_2$ (concatenation)
• $L^{*}$ is regular if $L$ is.

More on Regular Languages

1. The empty language is regular
2. The singleton of empty string is regular
3. The singleton of each character in the alpahbet is regular
4. Union
5. Concatenation
6. Kleene star
7. In fact, all set operations can be performed
   (On how to prove a language is regular)[http://cseweb.ucsd.edu/~clbailey/ClosureProofTemplate.htm]
   (On how to prove regular languages are closed under reverse)[http://web.cecs.pdx.edu/~hook/cs581sp11/reverse.pdf]
   Pumping Lemma Not really understand

• Injective: $a \neq a’ \rightarrow f(a) \neq f(a’)$
• Surjective: $\forall b\in B, \exists a\in A, f(a) = b$
• Bijective

$\mathbb{N} = \mathbb{Z}$
Countable = finite or countably infinite
Cantor’s Theorem
For any non-empty set $A$, $|A|\lt |P(A)|$. This can be proven by diagonalization. $S = a\in A: a\notin f(a)$ $S$ is defined by diagonalization so that $S$ cannot equal any $f(a)$.
Continuum Hypothesis (Hilbert’s 1st Problem)
There is no set $S$ such that $|\mathbb{N}|\lt |S|\lt |P(\mathbb{N})|$

String encoding: Computational problems can be serialized into a string

Computational Complexity

• Every multitape TM has an equivalent single tape TM.
• Running time depends on the particular model you choose
• Running time is defined as $T_A(n) = max{# \text{steps A takes on I}}$ (max input instance)
• intrinsic complexity is defined by $min$ (min algorithm).
• Entscheidungsproblem: Decide whether a given statement is valid with a given set of axioms
• To compute summations:
  • Rough bounding
  • Exact computation
  • Induction
  • Telescoping series ($\frac{1}{i(i+1)}$)
  • Comparison with an integral
• Master Method
  For $T(n) \le a\dot T(\frac{n}{b}) + O(n^d)$,
  • $a = b^d$, $O(n^dlog n)$
  • $a < b^d$, $O(n^d)$
  • $a > b^d$, $O(n^{log_ba})$

Prove Countability or Uncountability:

• countable cartesian product of countable sets
  • Prime factorization
• Countable union of countable sets
• Set of Finite Subsets of Countable Set
  • Induction

Strong Church-Turing Thesis: The intuitive notion of “efficiently computable” is captured by functions efficiently computable by a TM.

Polynomial time and the class P

$DTIME(T(n)) = $ the language decided by an $O(T(n))$ time algorithm.
$P=DTIME(n^k)$ union of all
$EXP=DTIME(2^{n^k})$ union of all
P is a subset of EXP.
We can prove that Polynomial time algorithms can solve every decidable problem
$HWTB$ is the language such that M takes at most $n^3$ steps. This cannot be decided in $O(n^2)$ steps, which can be proved with diagonalization algorithm.
Time Hierarchy Theorem
Let $T(n)$ be a time-constructible algorithm. $\epsilon > 0$. Then there is a problem which cannot be decided in time $T(n)$, but can be decided in time $T(n)^{1+\epsilon}$. $DTIME(T(n))$ is a PROPER subset of $DTIME(T(n)^{1+\epsilon})$.

Space Complexity

• Use two-tape TM that has a work tape and an input tape that is read-only.
  $DSPACE(T(n)) = $ the language decided by an $O(T(n))$ space algorithm.
  PSPACE, L is log space. L is a subset of PSPACE.
  Space Hierarchy Theorem
  If a TM uses $S(n)\ge log_2(n)$, then it decides the language using $\le 2^{O(S(n))}$ time (because of the number of possible configurations)
• $L\subset P$
• $PSPACE\subset EXP$
  Circuit Complexity
  A circuit family is an infinite answer to infinite number of questions
• The size of a circuit is the total number of gates, including inputs as gates too
• Circuit complexity is the size of the minimal circuit family that decides the language
  Circuit complexity is ALWAYS bounded by $2^n$.
  $f_A(x_1, x_2, …, x_n) = (x_1\wedge f_A(1, x_2, …, x_n))\wedge (\not x_1\wedge (f_A(0, x_2, .., x_n)))$
  This has recurrence $s(n) \le 2s(n-1)+5$.
  W.T.S.: There is a language L whose circuit complexity is at least $2^n/4n$.

1. Number of possible functions is $2^{2^n}$
2. Number of circuits of size s is $\le 2^{4slogs}$
   Claim 2: for each gate, 2 bits for its type, 2logs bits for which gates the inputs are from.

Basics

• Regular: all nodes have same degrees
• Walk
• Path: Walk with no repeated vertices
• Cycle: a walk from u to u where the only repeated vertex is u
• Tree: connected; n-1 edges; acyclic
• Local Search guarantees to get $\ge \frac{m}{2}$
  • Each vertex has $\ge \frac{deg(v)}{2}$ edges cut because otherwise we can flip its color to get more cuts

Problem: Identify all nodes reachable from s.
BFS, DFS, AFS
AFS finds a spanning tree rooted at s (bag, mark)
Why does AFS halt?
If we put edge in the bag, get a spanning tree.
Full AFS finds all connected components
CFS: Cheapest First Search
MST: subset of edges of minimum total cost such that all vertices connected
Prim: put the cheapest edge in the bag. If use Priority Queue, $O(Elog(E))$ run-time.
MST Cut Property e is the cheapest edge from S to not S, then must be in the MST.
Kruskal: Go through edges, add as long as it does not make cycles
Boruvka: Add the cheapest edges out of each c.c.

Matching

Bipartite Graph: there is a bipartition X and Y such that each edge connects x and y.
Matching: a subset of edges that do not share an endpoint.
Maximum Matching: A matching with largest number of edges
Perfect Matching: A matching that covers all vertices
Stable matching: There is no unstable pair(u, v not matched to each other, but they prefer each other to their current partners)
GS-algorithm: While a man is unmatched: propose to w(highest in the list)

• $O(n^2)$ (because number of proposals are $n^2$).
• Perfect Matching
• Stable
  GS always finds the Best Valid Partner
  Prove: Man always finds the best. Woman always finds the worst.

Maximum Matching

Augmenting path(with respect to matching M): edges alternate between in M and not in M.
Prove: If there is an aug. path, M is not maximum
Find Maximum Matching: start with an edge, find augment path, …
To find aug. path: direct edges in M from left to right.

NP and NP-completeness

NP: We have a simple proof to verify a solution

• length of proof is polynomial
• proof can be verified in polynomial time
  Cook-Levin Theorem: SAT is NP-complete

To show A is NP-complete:

1. A is in NP
2. Pick a NP-complete problem L
3. Show L reduces to A

NP: Nondeterminsitic Polynomial Time

C-hard: C can be reduced to A $\forall C \in C$
C-complete: C is in $C$.

Problems

• $HAM-CYCLE \le HAM-PATH$
  • For each edge $(u, v)$, add “tenacle” $u’ v’$.
• $TSP \le HAM-CYCLE$
  • Set weight of original edges to be $0$, others be $1$.
• $SUBSET-SUM \le 3-SAT$
  • For a $n$-var, $k$-clause 3-SAT, we build a table of vectors where lower $n$ bits, upper $k$ bits. If $x_i$ or $\not x_i$ then the lower $i$ bit is 1. If it is present in the $j$th clause, then upper $j$ is 1. For each upper column, we add two “slack rows” where one is 1, the other is 2.
  • If the $3-SAT$ is satisfiable, then we pick the rows representing true vars. We get first n bits 1s. We get each upper column 1, 2, or 3 (it cannot be 0 because there is at least 1 true var in each clause, it cannot be more than 3 because there are 3 vars in each clause). Then we pick corresponding slack rows to get all 4s on the upper bits. The reverse direction is similar.
• $3-SAT\le VC$
  • Construct a triplet for each clause, a pair for each variable $x$: $(x, \not x)$.
  • For a truth assignment, we pick 1 from the triplet to be true, the other 2 to be false. Add the false ones to the vertex cover. Add the true variable to the vertex cover. With-in edges are covered by true variables. Edges from pair to triplet have two cases. If the end in the triplet is selected(false), it is covered. If not(true), it is covered by the end in the pair.
  • For a n+2k vertex cover, 1 vertex in the triplet is not covered by itself but by the end in the pair, which is true. So this variable is true.
• $SAT\le 3-SAT$
  • Use parse tree to construct triplets with intermediate results.
• $SUBSET-SUM\le PARTITION$
  • populate $x_1, …, x_n, 2t-a$, where $a$ is the sum
• $SUBGRAPH-ISOMORPHIC$
  • CLIQUE reduces to this
• $HALTS$

Probability

• RandInt(m): 1, 2, 3, … m with $p=\frac{1}{m}$
• Bernoulli(p): 1 with $p=p$

outcome: A leaf in probability tree

Sample Space: Set of all outcomes

Event: A subset of outcomes

Law of Total Probability: $p[b] = p[a] p[b|a] + p[a^c] p[b|a^c]$

Independence of Multiple Events: for all subsets, for all size.

Random Variable: function from sample space to reals.

Indicator: R.V. x which is 1 when event A occurs, 0 otherwise.

1. Beef Stroganoff
   非常好吃好做的一道菜，用上了paprika，希望能结合中式调料配上米饭，加入剁椒和姜让他带上辣味应该会更好吃
2. Smoked Salmon Egg with Croissant
   没什么提升空间感觉，但是肯定好做好吃，smoked salmon怎么做都好吃
3. 腌笃鲜
   在美国应该是做不成了，但是很想学
4. 麻辣鸡
   处理一只嫩鸡，要么凉拌加上麻辣汁，要么用郫县豆瓣和剁椒炖，加上金针菇，香菇，青笋做一个锅

Communication Complexity

• $D_2(F)$ = min cost of a protocol computing F. (min of max)
• $R_2^e(F)$ min cost of a randomized protocol computing $F$.
• $0 \lte R \lte D \lte n+1$
• If TM decides L in $T(n)$ time and $S(n)$ space on input $3n$, then $T(n)*S(n)=\Omega(n^2)$
• $C^D(F)$ be the minimum number of monochromatic rectangles to partition
• $2^c \ge C^D(F)$

Markov Chain

The future is independent of the past, given the present

• stationary/invariant distribution
• Mean Recurrence Theorem
• transition matrix: $K[i, j] = Pr[X_1=j | X_0 = i]$
• Probability of being at state $i$ after $t$ steps: $\pi_t[i] = (\pi_0K^t)[i]$
• $E[T_{ii}] = E[#\text{steps to go from i to i}]$ = $1/\pi[i]$

Midterm 3 Review

Polynomial And Field

• There is a field with q elements iff q is a power of prime
• isomorphism: all fields with q elements have the same add&mult table, just renaming
• F[x] denotes the set of polynomials with variable x and coeffs. in field F. F[x] is not a field because division is not well-defined
• Polynomial division: deg(R(x)) < deg(B(x))
• A nonzero degree-d polynomial has at most d roots(depending on which field it may vary)
• There is exactly one poly of degree <= d which satisfies d+1 data points.
• Reed-Solomon Code: Sending as polynomials to avoid loss. 1. k erasures: send d+k+1 value-pairs 2. k corruptions: send d+2k+1 pairs, then there is a unique poly that differs with data at at most k points.

  Cryptography

• Euler’s Theorem & Fermat’s Little Theorem
• One-time pad (XOR); cannot be reused; Shannon’s Theorem: cannot have a pad smaller than the key size
• Diffie-Hellman Key Exchange: prime p, generator b, random r1 -p, b, $b^{r1}$> random r2 -> $b^{r2}$

• Public Secure Key: RSA

• Monte Carlo: possible to make errors, guarantee runtime

  • Min-cut: poly time. 1 - $\frac{1}{e}$
• Las Vegas : guarantee answer, possible worst running time
  • Quicksort

Primality testing

• Miller-Rabin: $O(n^2)$, with error rate $2^{-100}$
• To compute $A^B mod c$, repeatedly square $A$ and mod $c$. $O(n^2\log(n))$
• Reciprocal
• Euler totient: $\phi(x)$
• Euler’s theorem: $A^{\phi(M)} \equiv_M 1$, A,M relatively prime
• Fermat’s little theorem: $A^{p-1}\equiv_p 1$

Probability

• RandInt(m): 1, 2, 3, … m with $p=\frac{1}{m}$
• Bernoulli(p): 1 with $p=p$

outcome: A leaf in probability tree

Sample Space: Set of all outcomes

Event: A subset of outcomes

Law of Total Probability: $p[b] = p[a] p[b|a] + p[a^c] p[b|a^c]$

Independence of Multiple Events: for all subsets, for all size.

Random Variable: function from sample space to reals.

Indicator: R.V. x which is 1 when event A occurs, 0 otherwise.

NP and NP-completeness

NP: We have a simple proof to verify a solution

• length of proof is polynomial
• proof can be verified in polynomial time
  Cook-Levin Theorem: SAT is NP-complete

To show A is NP-complete:

1. A is in NP
2. Pick a NP-complete problem L
3. Show L reduces to A

NP: Nondeterminsitic Polynomial Time

C-hard: C can be reduced to A $\forall C \in C$
C-complete: C is in $C$.

Midterm Review

Types of problems

• Prove big-oh or not big-oh (exists…for all; for all… exists).
• Circuit family
• Fast binary conversion, Nice language, paren algorithm, sorting $\frac{3n}{2}$
• !x1, a, b; x2, b, c; !x3, c, d; (1/3 SAT)

Time Complexity, NP

• A language is in NP iff it can be decided by an NTM in polynomial time
  • Non-deterministically guess its verifier
  • Construct the verifier with the accepting path in NTM
• SAT $\in$ P iff P = NP

• 3SAT reduce to CLIQUE (triples with two exceptions)

  Cook-Levin Theorem
  SAT is NP-complete

• 3SAT is NP-c (reduce to SAT)

• CLIQUE is NP-c
• V-C is NP-c (recitation)
• HAMPATH is NP-c (3SAT, diamond, zigzag, add additional edge when $c_j$ contains $\not x_i$)
• UHAMPATH is NP-c (HAMPATH by disassembling)
• SUBSET SUM(3SAT)

Space Complexity

P $\subset$ NP $\subset$ PSPACE = NPSPACE $\subset$ EXPTIME

• If A can be decided in $t(n)$, then A has circuit complexity $t(n)^2$ (Reverse also true?)
• Circuit-SAT is NP-C
• Do exerices 9

Problems

• $HAM-CYCLE \le HAM-PATH$
  • For each edge $(u, v)$, add “tenacle” $u’ v’$.
• $TSP \le HAM-CYCLE$
  • Set weight of original edges to be $0$, others be $1$.
• $SUBSET-SUM \le 3-SAT$
  • For a $n$-var, $k$-clause 3-SAT, we build a table of vectors where lower $n$ bits, upper $k$ bits. If $x_i$ or $\not x_i$ then the lower $i$ bit is 1. If it is present in the $j$th clause, then upper $j$ is 1. For each upper column, we add two “slack rows” where one is 1, the other is 2.
  • If the $3-SAT$ is satisfiable, then we pick the rows representing true vars. We get first n bits 1s. We get each upper column 1, 2, or 3 (it cannot be 0 because there is at least 1 true var in each clause, it cannot be more than 3 because there are 3 vars in each clause). Then we pick corresponding slack rows to get all 4s on the upper bits. The reverse direction is similar.
• $3-SAT\le VC$
  • Construct a triplet for each clause, a pair for each variable $x$: $(x, \not x)$.
  • For a truth assignment, we pick 1 from the triplet to be true, the other 2 to be false. Add the false ones to the vertex cover. Add the true variable to the vertex cover. With-in edges are covered by true variables. Edges from pair to triplet have two cases. If the end in the triplet is selected(false), it is covered. If not(true), it is covered by the end in the pair.
  • For a n+2k vertex cover, 1 vertex in the triplet is not covered by itself but by the end in the pair, which is true. So this variable is true.
• $SAT\le 3-SAT$
  • Use parse tree to construct triplets with intermediate results.
• $SUBSET-SUM\le PARTITION$
  • populate $x_1, …, x_n, 2t-a$, where $a$ is the sum
• $SUBGRAPH-ISOMORPHIC$
  • CLIQUE reduces to this
• $HALTS$

Basics

• Regular: all nodes have same degrees
• Walk
• Path: Walk with no repeated vertices
• Cycle: a walk from u to u where the only repeated vertex is u
• Tree: connected; n-1 edges; acyclic
• Local Search guarantees to get $\ge \frac{m}{2}$
  • Each vertex has $\ge \frac{deg(v)}{2}$ edges cut because otherwise we can flip its color to get more cuts

Problem: Identify all nodes reachable from s.
BFS, DFS, AFS
AFS finds a spanning tree rooted at s (bag, mark)
Why does AFS halt?
If we put edge in the bag, get a spanning tree.
Full AFS finds all connected components
CFS: Cheapest First Search
MST: subset of edges of minimum total cost such that all vertices connected
Prim: put the cheapest edge in the bag. If use Priority Queue, $O(Elog(E))$ run-time.
MST Cut Property e is the cheapest edge from S to not S, then must be in the MST.
Kruskal: Go through edges, add as long as it does not make cycles
Boruvka: Add the cheapest edges out of each c.c.

Matching

Bipartite Graph: there is a bipartition X and Y such that each edge connects x and y.
Matching: a subset of edges that do not share an endpoint.
Maximum Matching: A matching with largest number of edges
Perfect Matching: A matching that covers all vertices
Stable matching: There is no unstable pair(u, v not matched to each other, but they prefer each other to their current partners)
GS-algorithm: While a man is unmatched: propose to w(highest in the list)

• $O(n^2)$ (because number of proposals are $n^2$).
• Perfect Matching
• Stable
  GS always finds the Best Valid Partner
  Prove: Man always finds the best. Woman always finds the worst.

Maximum Matching

Augmenting path(with respect to matching M): edges alternate between in M and not in M.
Prove: If there is an aug. path, M is not maximum
Find Maximum Matching: start with an edge, find augment path, …
To find aug. path: direct edges in M from left to right.