# CS580 Note

## GS Matching

Claim: Algorithm terminates after at most $n^2$ iterations of while loop.

Claim: All men and women get matched.

Claim: No unstable pairs.

Claim: GS matching $S^*$ is man-optimal

Claim: GS finds woman-pessimal stable matching $S^*$.

## Mergesort

Claim: $T(n) = 2T(n/2) + n = O(n \log_2 n)$

## Quicsort

Theorem: The worst-case running time of Quicksort is $\Omega(n^2)$.

Theorem: The worst-case running time of Quicksort is $O(n^2)$.

Theorem: The best-case running time of Quicksort is $O(n \log n)$.

Theorem: The randomized Quicksort has the expected running time of $\Theta(n \log n)$.

## Lower bound of sorting algorithms:

Theorem: Any deterministic comparison-based sorting algorithm must take $\Omega(n \log n)$ steps.

## Min/Max & Randomized Selection:

Theorem: Random selection with randomized partition has $O(n)$ expected time.

Prove or disprove that we can do better than $3n/2 -2$ comparisons ($3n/2 - 2$ is the lower bound).

Lemma: Let $S$ be a set of elements. Given a set $X$ of comparison queries about elements from $S$ with their Yes/No answers, construct a directed graph with vertices $S$ for each $(x, y)$ involved in a query, and edge $x \rightarrow y$ if the answer of that query was $x > y$, then there is a permutation of S compatible with the queries in $X$ if and only if the graph is a DAG.

## Median of Medians:

Proof that there are at least $3n/10 - 6$ elements smaller or larger than the median of medians.

Proof that the upper bound of deterministic selection algorithm with median of medians selection is $O(n)$.

## Find Max in Rounds:

Lemma: A graph with $n$ nodes and fewer than $s$ range has an independent set of size at least $\frac{n^2}{8s}$.

## Dijkstra

Proof by invariant that Dijkstra is correct:
- Invariant: For each node $u \in S$, $d(u)$ is the length of the shortest $s$-$u$ path

## Minimum Spanning Tree

Claim: A cycle and a cutset intersect in an even number of edges.

Cut property: Let $S$ be any subset of nodes, and let $e$ be the min cost edge with exactly one endpoint in $S$, then the MST $T*$ contains $e$.

Cycle property: Ket $C$ be any cycle in $G$, and let $f$ be the max cost edge belonging to $C$. Then the MST $T*$ does not contain $f$.

## Network Flow Basic

Flow Value Lemma: Let $f$ be any flow, and let $(A, B)$ be any s-t cut. Then the net flow sent across the cut is equal to the amount leaving s.

Weak Duality: Let f be any flow and let $(A, B)$ be any s-t cut. Then the value of the flow is at most the capacity of the cut.

Corollary: Let $f$ be any flow, and let $(A, B)$ be any cut. If $v(f) = cap(A, B)$, then $f$ is a max flow and $(A, B)$ is a min cut.

Lemma: Let $f'$ be the flow resulting from $Augment(f, P)$. Then $f$ is a valid flow in $G$.

Lemma 1: At every intermidiate stage of the Ford-Fulkerson Algorithm, the flow values $\{f(e)\}$ and the residual capacities in $G_f$ are integers.

Lemma 2: Let $f$ be a flow in $G$, and let $P$ be a simple s-t path in $G_f$. Then $v(f') = v(f) + bottleneck(P, f)$. and since $bottleneck(P, f) > 0$, we have $v(f') > v(f)$.

Lemma 3: Let $C = \Sigma_{e\ out\ of\ s}c_e$ and suppose all capacities in the flow network are integers. Then the Ford-Fulkerson Algorithm terminates in at most $C$ iterations of the while loop.

Proof that min cut is the set of nodes reachable from $s$ in residual graph.

## Network Flow Applications

Max-cardinality Matching Theorem: 1-1 correspondence between matchings of cardinality $k$ in $G$ and integral flows of value $k$ in $G'$.

Perfect Matching Theorem: Let $G=(L \cup R, E)$ be a bipartite graph with $|L| = |R|$. Then, graph $G$ has a perfect matching iff $|N(S)| \ge |S|$ for all subsets $S \subset L$.

K-Regular Bipartite Graph: prove that it has a stable matching

Edge-disjoint path corollary: max-flow formulation solves edge-disjoint path problem.

Menger's theorem: The max number of edge-disjoint s-t path equals to the min number of edges whose removal disconnects $t$ from $s$.

Edge-disjoint paths in undirected graphs Lemma: In any flow network, there exists a maximum folw $f$ in which for each pair of antiparallel edges $e$ and $e'$: either $f(e) = 0$ or $f(e') = 0$ or both.