Section B: Exam-Ready Theory (The Rigor)

• Class P (Polynomial Time): The set of decision problems that can be solved by a deterministic algorithm in polynomial time $O(n^k)$. (e.g., Shortest Path, Merge Sort).
• Class NP (Non-Deterministic Polynomial Time): The set of decision problems that can be verified by a deterministic algorithm in polynomial time. If you are given a “certificate” (a proposed solution), you can check if it is correct in $O(n^k)$ time.
• Class NP-Hard: A problem $X$ is NP-Hard if every problem $Y$ in NP can be reduced to $X$ in polynomial time ($Y \leq_p X$). It means $X$ is at least as hard as the hardest problems in NP. (Note: $X$ itself does not have to be in NP).
• Class NP-Complete: A problem is NP-Complete if it satisfies two conditions:
  1. It is in NP.
  2. It is NP-Hard. (e.g., TSP, Clique, Vertex Cover, 3-CNF-SAT).

Section B: Exam-Ready Theory (The Rigor)

Feature	Las Vegas Algorithms	Monte Carlo Algorithms
Output Correctness	Always produces the correct and optimal output (Probability of correctness = 1).	May produce incorrect output with some probability of failure.
Running Time	The running time is a random variable and is NOT bounded.	Runs for a fixed, deterministic number of steps (Time is bounded).
Trade-off	Gambles with computing resources (Time/Space).	Gambles with the accuracy of the result.
Examples	Randomized Quick Sort.	Miller-Rabin Primality Test, checking for a majority element.

Section B: Exam-Ready Theory (The Rigor)

• Deterministic Quick Sort Issue: If the input array is already sorted or reverse-sorted, picking the first element as the pivot results in unbalanced partitions ($0$ and $n-1$ elements). This degrades the time complexity to $O(n^2)$.
• Randomized Quick Sort Algorithm:

  Algorithm randQuickSort(A[], low, high) {
      if low >= high, then EXIT
      While pivot 'x' is not a Central Pivot:
          1. Choose uniformly at random an element 'x' from A[low..high].
          2. Count elements smaller than 'x' (sc) and greater than 'x' (gc).
          3. If sc >= n/4 and gc >= n/4, then 'x' is a central pivot. Break loop.
      Partition A[low..high] using 'x'. Let index of 'x' be pos.
      randQuickSort(A, low, pos-1)
      randQuickSort(A, pos+1, high)
  }

Section B: Exam-Ready Theory (The Rigor)

• Definition: Approximation algorithms return near-optimal solutions in polynomial time for NP-Complete optimization problems.
• Bin Packing Problem: Given $n$ items of sizes $S_1, S_2, \dots, S_n$ and bins of capacity $C$, assign items to bins to minimize the number of used bins.
• Lower Bound: Minimum bins $\geq \lceil \text{Total Weight} / \text{Bin Capacity} \rceil$.
• Approximation Ratio:
  • First Fit (FF): $FF(I) \leq \frac{17}{10} OPT(I) + 2$.
  • First Fit Decreasing (FFD): $FFD(I) \leq \frac{11}{9} OPT(I) + \frac{6}{9}$.

Section B: Exam-Ready Theory (The Rigor)

Steps to prove a problem $X$ is NP-Complete:

1. Prove $X \in NP$ (Write a polynomial time verifier).
2. Prove $X \in NP-Hard$ (Reduce a known NP-Complete problem $Y$ to $X$ in polynomial time: $Y \leq_p X$).

Proof: CLIQUE is NP-Complete

Step 1: Prove CLIQUE is in NP

• Certificate: A set $V'$ of $k$ vertices.
• Verifier:
  1. Check if $|V'| = k$.
  2. For every pair of vertices $u, v \in V'$, check if the edge $(u, v)$ exists in the graph $G$.
• Since checking edges takes $O(k^2)$ time (polynomial), CLIQUE is in NP.

Step 2: Prove CLIQUE is NP-Hard (Reduction from 3-CNF-SAT)

• Let $\Phi = C_1 \land C_2 \dots \land C_k$ be a boolean formula in 3-CNF with $k$ clauses. Each clause has 3 literals: $(l_1 \lor l_2 \lor l_3)$.
• Construct Graph $G$:
  1. For each clause, create a “triple” of vertices in $G$ corresponding to its 3 literals.
  2. Connect vertex $v_{i}$ to vertex $v_{j}$ with an edge IF AND ONLY IF:
     • They belong to different clauses (different triples).
     • They are not logical negations of each other (e.g., do not connect $x$ and $\neg x$).
• Equivalence: The boolean formula $\Phi$ is satisfiable IF AND ONLY IF the constructed graph $G$ has a CLIQUE of size exactly $k$. (Picking one true literal per clause forms a fully connected $k$-clique).
• Since constructing this graph takes polynomial time, 3-CNF-SAT $\leq_p$ CLIQUE.

Section B: Exam-Ready Theory (The Rigor)

Proof: VERTEX COVER is NP-Complete

Step 1: Prove VERTEX COVER is in NP

• Certificate: A subset of vertices $V'$.
• Verifier:
  1. Check if $|V'| \leq k$.
  2. For every edge $(u, v)$ in the graph $G$, check if $u \in V'$ OR $v \in V'$.
• Since checking all edges takes $O(E)$ time, VERTEX COVER is in NP.

Step 2: Prove VERTEX COVER is NP-Hard (Reduction from CLIQUE)

• Concept: A clique in a graph $G$ is a vertex cover in the complement graph $\bar{G}$ (with a size adjustment).
• Reduction Algorithm:
  1. Given an instance of CLIQUE $(G, k)$.
  2. Construct the complement graph $\bar{G}$ (where an edge exists in $\bar{G}$ iff it does NOT exist in $G$).
  3. A subset $V'$ is a CLIQUE of size $k$ in $G$ IF AND ONLY IF the subset $V - V'$ is a VERTEX COVER of size $|V| - k$ in $\bar{G}$.
• Since constructing the complement graph takes polynomial time, CLIQUE $\leq_p$ VERTEX COVER.