Short Notes — Any Two (Covering All Four for Choice)

(i) Asymptotic Notations (see Q36/Q88)

$O$ upper, $\Omega$ lower, $\Theta$ tight, $o$/$\omega$ strict. Hierarchy $O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)$. Used to compare algorithms independent of hardware; max rule for polynomials etc.

(ii) Clique Decision Problem

Given undirected $G(V,E)$ and integer $k$, does $G$ contain a clique (complete subgraph) of size ≥ $k$?

• NP-complete: In NP (certificate = $k$ vertices, check all $\binom{k}{2}$ edges in $O(k^2)$) + NP-hard via reduction from 3-SAT or Vertex Cover (complement: $G$ has clique $k$ ⇔ complement $\bar G$ has vertex cover $V-k$). Brute $O(V^k)$ exponential; no known polytime.
• Applications: clustering, social networks.

(iii) Max-Flow Min-Cut Theorem (Ford-Fulkerson)

For network with source $s$, sink $t$, capacities $c$, value of max flow = capacity of min $s-t$ cut (set $S∋s$, $T∋t$ partition, capacity sum of edges $S→T$). Proof via Ford-Fulkerson: flow maximal iff no augmenting path in residual graph → reachable set from $s$ defines min cut with equal capacity. Consequences: integrality (if capacities integer, max flow integer), duality for bipartite matching, etc. Used to prove correctness of Ford-Fulkerson $O(VE^2)$ (Edmonds-Karp) etc.

(iv) Union-Find (Disjoint Set Union, DSU) Algorithm

Maintains partition of elements into disjoint sets with operations:

• MakeSet(x): $parent[x]=x$, rank/size 0
• Find(x): with path compression → $O(α(n))$
• Union(x,y): by rank/size → $O(α(n))$
  Sequence of $m$ ops on $n$ elements → $O(mα(n))$ almost constant ($α$ inverse Ackermann <5 for practical $n$).
  Uses: Kruskal MST cycle check, connected components, offline LCA. Pseudo:

Find(x): if parent[x]!=x: parent[x]=Find(parent[x]); return parent[x]
Union(a,b): ra=Find(a), rb=Find(b); if ra==rb return; if rank[ra]<rank[rb] swap; parent[rb]=ra; if rank equal rank[ra]++