Section B: Exam-Ready Theory (The Rigor)

• Definition: A control abstraction is a procedure whose general flow is clear, but whose primary operations are left undefined. The Greedy method builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
• Feasibility: A solution is feasible if it satisfies the problem’s constraints (e.g., doesn’t exceed the knapsack capacity).
• Optimality: An optimal solution is a feasible solution that maximizes or minimizes a given objective function.
• Algorithm Structure:

  Greedy(a, n) {
      solution = Φ;
      for i=1 to n do {
          x = Select(a);
          if Feasible(solution, x) then
              solution = Union(solution, x);
      }
      return solution;
  }

Section B: Exam-Ready Theory (The Rigor)

• Definition: An algorithm design paradigm that recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
• Three Steps:
  1. Divide: Break the problem $P$ into smaller instances $P_1, P_2, \dots, P_k$.
  2. Conquer: Solve the sub-problems recursively.
  3. Combine: Merge the sub-solutions into a single solution for $P$.
• Algorithm Structure:

  Algorithm DAndC(P) {
      if Small(P) then
          return S(P);
      else {
          Divide P into P1, P2... Pk;
          apply DAndC to sub-problems;
          return Combine(DAndC(P1)... DAndC(Pk));
      }
  }

Section B: Exam-Ready Theory (The Rigor)

• Problem Statement: Given $n$ objects, each with a weight $W_i$ and a profit $P_i$, and a knapsack of capacity $m$. Find the fractions $X_i \in [0, 1]$ for each object such that the total weight $\sum (W_i X_i) \leq m$ and the total profit $\sum (P_i X_i)$ is maximized.
• Greedy Strategy:
  1. Calculate the profit-to-weight ratio for all items: $Ratio_i = P_i / W_i$.
  2. Sort the items in descending order of this ratio.
  3. Iterate through the sorted items:
     • If the item fits entirely, take it ($X_i = 1$) and reduce capacity.
     • If it doesn’t fit entirely, take the remaining fraction of it ($X_i = \text{Remaining Capacity} / W_i$) and terminate.
• Time Complexity: $O(n \log n)$ due to the sorting step.

Section B: Exam-Ready Theory (The Rigor)

• Spanning Tree: A subgraph of an undirected connected graph $G=(V, E)$ that includes all vertices $V$ but has exactly $V-1$ edges and no cycles.
• Minimum Spanning Tree (MST): A spanning tree with the minimum possible total edge weight.
• Kruskal’s Strategy:
  1. Treat every vertex as its own isolated set (forest of trees).
  2. Sort all edges in the graph in ascending order of their weight.
  3. Iterate through the sorted edges:
     • If the edge connects two vertices in different sets (using Union-Find / Disjoint Sets), add it to the MST and Union the sets.
     • If it connects vertices in the same set, adding it would form a cycle, so discard it.
  4. Stop when $V-1$ edges have been added.
• Time Complexity: $O(|E| \log |E|)$ dominated by sorting the edges using a min-heap.

Section B: Exam-Ready Theory (The Rigor)

• Problem: Given a weighted graph $G(V,E)$ with non-negative edge weights, find the shortest path from a single source vertex $S$ to all other vertices.
• Algorithm Strategy (Relaxation):
  1. Initialize dist[] = ∞, dist[S] = 0.
  2. Maintain set $Q$ of unvisited nodes.
  3. While $Q$ is not empty:
     • Extract $u$ with min dist.
     • For each neighbor $v$ of $u$:
       • alt = dist[u] + weight(u, v).
       • If alt < dist[v], update dist[v] = alt.
• Time Complexity: $O(V^2)$ with array, $O(E \log V)$ with min-heap.

Section B: Exam-Ready Theory (The Rigor)

• Algorithm Strategy:
  1. Divide: Find the midpoint mid = (low + high) / 2.
  2. Conquer: Recursively call MergeSort(low, mid) and MergeSort(mid+1, high).
  3. Combine: Call Merge(low, mid, high) to weave the two sorted halves into a single temporary array, then copy it back.
• Recurrence Relation:
  • Dividing takes $O(1)$.
  • Recursively sorting two halves takes $2T(n/2)$.
  • Merging two arrays of size $n/2$ takes $O(n)$ comparisons.
  • Equation: $T(n) = 2T(n/2) + cn$
• Time Complexity: Solving the recurrence (via Master’s Theorem or Recursion Tree) yields exactly $O(n \log n)$ in the Best, Average, and Worst cases.