COMPREHENSIVE NOTES ON

DESIGN AND ANALYSIS OF

ALGORITHMS
Based on: Introduction to Algorithms (CLRS) — 3rd Edition
Cormen · Leiserson · Rivest · Stein

Modules Covered:
Module 1: Introduction to Algorithms | Module 2: Greedy Methods & String Matching
Module 3: Dynamic Programming & Maximum Flow | Module 4: Backtracking & Branch-and-Bound
Module 5: Approximation & NP-Completeness
MODULE 1: INTRODUCTION TO ALGORITHMS
Total Hours: 8 | Reference: CLRS Chapters 1, 2, 3, 4

1.1 Role of Algorithms

What is an Algorithm?
📌 Algorithm: A well-defined computational procedure that takes some value(s) as input and produces some
value(s) as output. It is a finite sequence of computational steps that transforms the input into the output.

An algorithm must satisfy:

• Input: Zero or more quantities are externally supplied
• Output: At least one quantity is produced
• Definiteness: Each instruction is clear and unambiguous
• Finiteness: The algorithm terminates after a finite number of steps
• Effectiveness: Each step must be basic enough to be carried out

Algorithm as Technology
Algorithms are a technology, just like hardware, operating systems, or networking. Total system performance
depends on:
• Choosing efficient algorithms (time and space complexity)
• Hardware speed
• Software quality
Example: Insertion Sort runs in Θ(n²) time. Merge Sort runs in Θ(n log n). For n = 10⁷, merge sort is ~6000× faster
even on slower hardware.

Insertion Sort
Problem: Sort a sequence of n numbers into nondecreasing order.
Idea: Like sorting playing cards — pick one card at a time and insert it into its correct position in the already-
sorted portion.

⚙ ALGORITHM: INSERTION-SORT(A)
INSERTION-SORT(A)
for j = 2 to [Link]
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

Trace Example: A = [5, 2, 4, 6, 1, 3]

 • j=2: key=2, compare 5>2 → shift → [2,5,4,6,1,3]
• j=3: key=4, compare 5>4 → shift, 2<4 → [2,4,5,6,1,3]
• j=4: key=6, 5<6 → [2,4,5,6,1,3]
• j=5: key=1, shift 6,5,4,2 → [1,2,4,5,6,3]
• j=6: key=3, shift 6,5,4 → [1,2,3,4,5,6]

Loop Invariant for Insertion Sort

🔷 Loop Invariant: At the start of each iteration of the for loop, subarray A[1..j-1] contains the elements
originally in A[1..j-1], but in sorted order.
Proof of Correctness via Loop Invariant:
• Initialization: Before j=2, A[1..1] has one element — trivially sorted. ✓
• Maintenance: Each iteration maintains the invariant by inserting A[j] into correct position. ✓
• Termination: When j = n+1, A[1..n] is sorted. ✓

Complexity Analysis of Insertion Sort

Best Case: Θ(n) — Array already sorted; inner while loop never executes
Worst Case: Θ(n²) — Array sorted in reverse; inner while loop executes j-1 times
Average Case: Θ(n²) — On average, half the elements are shifted
Space: O(1) — In-place algorithm (sorts within the array itself)

Selection Sort
Idea: Find the minimum element in the unsorted portion and place it at the beginning.

⚙ ALGORITHM: SELECTION-SORT(A)
SELECTION-SORT(A)
for i = 1 to [Link] - 1
min_idx = i
for j = i+1 to [Link]
if A[j] < A[min_idx]
min_idx = j
swap A[i] with A[min_idx]

Trace Example: A = [64, 25, 12, 22, 11]

• i=1: min=11 at pos 5 → swap → [11, 25, 12, 22, 64]
• i=2: min=12 at pos 3 → swap → [11, 12, 25, 22, 64]
• i=3: min=22 at pos 4 → swap → [11, 12, 22, 25, 64]
• i=4: min=25 already in position → [11, 12, 22, 25, 64]

Best/Worst/Average Case: Θ(n²) — Always performs n(n-1)/2 comparisons

Space: O(1) — In-place
Note: Selection sort does at most n-1 swaps; insertion sort may do O(n²) shifts
1.2 Asymptotic Notations
Asymptotic analysis describes algorithm efficiency for large input sizes (n → ∞), ignoring constants and lower-
order terms.

Θ-Notation (Theta — Tight Bound)

📌 Θ(g(n)): f(n) = Θ(g(n)) iff ∃ positive constants c₁, c₂, n₀ such that 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀
Meaning: f(n) grows at the same rate as g(n). It provides a tight (exact) bound.
Example: f(n) = 3n² + 5n + 2 = Θ(n²)
• Upper: 3n² + 5n + 2 ≤ 4n² for all n ≥ 10 (c₂=4)
• Lower: 3n² + 5n + 2 ≥ 3n² for all n ≥ 1 (c₁=3)

O-Notation (Big-O — Upper Bound)

📌 O(g(n)): f(n) = O(g(n)) iff ∃ positive constants c, n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀
Meaning: f(n) grows no faster than g(n). Used to describe the worst case.
Examples: 3n² + 5n = O(n²), O(n³), O(2ⁿ) — but Θ(n²) is most precise

Ω-Notation (Omega — Lower Bound)

📌 Ω(g(n)): f(n) = Ω(g(n)) iff ∃ positive constants c, n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀
Meaning: f(n) grows at least as fast as g(n). Used to describe the best case.
Example: Insertion sort is Ω(n) — always looks at each element at least once.

o-Notation (Little-o — Strict Upper Bound)

📌 o(g(n)): f(n) = o(g(n)) iff for ANY positive constant c, ∃ n₀ such that 0 ≤ f(n) < c·g(n) for all n ≥ n₀
Meaning: f(n) grows strictly slower than g(n). Example: 2n = o(n²)

ω-Notation (Little-omega — Strict Lower Bound)

📌 ω(g(n)): f(n) = ω(g(n)) iff for ANY positive constant c, ∃ n₀ such that 0 ≤ c·g(n) < f(n) for all n ≥ n₀
Meaning: f(n) grows strictly faster than g(n). Example: n² = ω(n)

Summary Table: Common Growth Rates

Notation Meaning Intuition Example
Θ(g(n)) Tight bound f grows like g n² + n = Θ(n²)

O(g(n)) Upper bound f grows ≤ g n = O(n²)

Ω(g(n)) Lower bound f grows ≥ g n² = Ω(n)

o(g(n)) Strict upper f grows < g n = o(n²)

ω(g(n)) Strict lower f grows > g n² = ω(n)

Recurrence Relations
A recurrence equation describes the running time of a recursive algorithm. Methods to solve them:

1. Substitution Method
Guess a bound and prove it by induction.
Example: T(n) = 2T(n/2) + n
• Guess: T(n) = O(n log n)
• Assume T(n/2) ≤ c(n/2)log(n/2)
• Substitute: T(n) ≤ 2·c(n/2)log(n/2) + n = cn·log(n/2) + n = cn·log n − cn + n ≤ cn·log n for c ≥ 1
• Proved: T(n) = O(n log n) ✓

2. Recursion-Tree Method
Draw a tree where each node represents the cost of one recursive call. Sum costs at each level.
Example: T(n) = 3T(n/4) + Θ(n²)
• Level 0: n² (root)
• Level 1: 3 nodes, each (n/4)² → 3n²/16
• Level 2: 9 nodes, each (n/16)² → 9n²/256
• Geometric series with ratio 3/16 < 1 → sum is O(n²)

3. Master Theorem
🔷 Master Theorem: For T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, compare f(n) with n^(log_b(a)):
Case 1: If f(n) = O(n^(log_b(a) − ε)) for some ε > 0 → T(n) = Θ(n^(log_b(a)))
Case 2: If f(n) = Θ(n^(log_b(a))) → T(n) = Θ(n^(log_b(a)) · log n)
Case 3: If f(n) = Ω(n^(log_b(a) + ε)) and af(n/b) ≤ cf(n) → T(n) = Θ(f(n))

Master Theorem Examples:

• T(n) = 2T(n/2) + n: a=2, b=2, f(n)=n, n^(log₂2)=n → Case 2 → T(n) = Θ(n log n) [Merge Sort]
• T(n) = 9T(n/3) + n: a=9, b=3, n^(log₃9)=n², f(n)=n=O(n²⁻¹) → Case 1 → T(n) = Θ(n²)
• T(n) = 3T(n/4) + n log n: n^(log₄3)≈n^0.79, f(n)=n log n=Ω(n^0.79+0.21) → Case 3 → T(n)=Θ(n log n)

1.3 Divide and Conquer

📌 Divide and Conquer: A paradigm that: (1) DIVIDES the problem into subproblems, (2) CONQUERS by
solving subproblems recursively, (3) COMBINES solutions to subproblems into the overall solution.

Merge Sort
Divide array into two halves, recursively sort each half, then merge.

⚙ ALGORITHM: MERGE-SORT(A, p, r)
MERGE-SORT(A, p, r)
if p < r
q = floor((p + r) / 2)
MERGE-SORT(A, p, q)
 MERGE-SORT(A, q+1, r)
MERGE(A, p, q, r)

MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
create arrays L[1..n1+1] and R[1..n2+1]
for i = 1 to n1: L[i] = A[p + i - 1]
for j = 1 to n2: R[j] = A[q + j]
L[n1+1] = ∞ (sentinel)
R[n2+1] = ∞ (sentinel)
i = 1; j = 1
for k = p to r
if L[i] ≤ R[j]
A[k] = L[i]; i = i + 1
else
A[k] = R[j]; j = j + 1

Recurrence: T(n) = 2T(n/2) + Θ(n)

By Master Theorem Case 2: T(n) = Θ(n log n)
Time: Θ(n log n) all cases | Space: O(n) | Stable: Yes

Maximum Subarray Problem

Find the contiguous subarray with the maximum sum. Example: [−2, 1, −3, 4, −1, 2, 1, −5, 4] → max subarray
[4,−1,2,1] with sum 6.

⚙ ALGORITHM: FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -∞
sum = 0
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -∞
sum = 0
for j = mid+1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, left-sum + right-sum)

FIND-MAXIMUM-SUBARRAY(A, low, high)

if low == high: return (low, high, A[low]) // base case
mid = floor((low + high) / 2)
(ll, lr, lsum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
 (rl, rr, rsum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
(cl, cr, csum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
return whichever of (ll,lr,lsum),(rl,rr,rsum),(cl,cr,csum) has greatest sum

Recurrence: T(n) = 2T(n/2) + Θ(n) → T(n) = Θ(n log n)

Note: Kadane's algorithm solves this in O(n) using dynamic programming.

Closest Pair of Points

Given n points in a 2D plane, find the pair with minimum Euclidean distance.
Brute force: O(n²). Divide and Conquer achieves O(n log n).

⚙ ALGORITHM: CLOSEST-PAIR(P) — Divide and Conquer

CLOSEST-PAIR(P):
Sort points by x-coordinate
if |P| ≤ 3: brute force, return closest pair
mid = P[n/2]
PL = P[1..n/2]; PR = P[n/2+1..n]
dL = CLOSEST-PAIR(PL)
dR = CLOSEST-PAIR(PR)
d = min(dL, dR)
// Check strip around midpoint
strip = all points within distance d of vertical line x = mid.x
Sort strip by y-coordinate
for each point in strip, compare with next 7 points
dstrip = min distance in strip
return min(d, dstrip)

Key Insight: Only 7 points need to be checked in the strip for each point (geometric proof).
Time: O(n log n) — T(n) = 2T(n/2) + O(n log n) with pre-sorting

Strassen's Matrix Multiplication

Naive matrix multiplication of two n×n matrices requires Θ(n³).
Strassen's algorithm reduces this to Θ(n^(log₂7)) ≈ Θ(n^2.807).

Standard Divide and Conquer (8 multiplications):

• Divide each n×n matrix into four n/2 × n/2 sub-matrices
• T(n) = 8T(n/2) + Θ(n²) → Case 1 of Master Theorem → T(n) = Θ(n³) — no improvement

⚙ ALGORITHM: STRASSEN'S ALGORITHM (7 multiplications)

Given A = [A₁₁ A₁₂; A₂₁ A₂₂], B = [B₁₁ B₁₂; B₂₁ B₂₂]

Compute 7 products:
M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)(B₁₁)
M₃ = (A₁₁)(B₁₂ − B₂₂)
 M₄ = (A₂₂)(B₂₁ − B₁₁)
M₅ = (A₁₁ + A₁₂)(B₂₂)
M₆ = (A₂₁ − A₁₁)(B₁₁ + B₁₂)
M₇ = (A₁₂ − A₂₂)(B₂₁ + B₂₂)

Result C = A × B:
C₁₁ = M₁ + M₄ − M₅ + M₇
C₁₂ = M₃ + M₅
C₂₁ = M₂ + M₄
C₂₂ = M₁ − M₂ + M₃ + M₆

Recurrence: T(n) = 7T(n/2) + Θ(n²)

By Master Theorem Case 1: n^(log₂7) ≈ n^2.807 > n², so T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)

Quick Sort
Divide: Partition array around a pivot element. Conquer: Recursively sort the two halves.

⚙ ALGORITHM: QUICKSORT(A, p, r)
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x = A[r] // pivot
i = p - 1
for j = p to r-1
if A[j] ≤ x
i = i + 1
swap A[i] with A[j]
swap A[i+1] with A[r]
return i + 1

Trace of PARTITION([2,8,7,1,3,5,6,4], 1, 8) with pivot=4:

• Pivot=4. Compare each element with pivot.
• After partition: [2,1,3,4,7,8,5,6] — elements ≤4 on left, >4 on right

Best Case: Θ(n log n) — Pivot always splits array in half

Worst Case: Θ(n²) — Pivot always the min or max (sorted/reverse-sorted array)
Average Case: Θ(n log n) — Expected over all input permutations
Space: O(log n) stack space (in-place sorting)

Randomized QuickSort
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
 swap A[i] with A[r]
return PARTITION(A, p, r)
By choosing a random pivot, expected running time is Θ(n log n) for any input.

Merge Sort (for Selection in Linear Time)

Related: Finding the kth smallest element (ORDER STATISTIC):

⚙ ALGORITHM: RANDOMIZED-SELECT(A, p, r, i)
RANDOMIZED-SELECT(A, p, r, i) // Find ith smallest
if p == r: return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1 // k = rank of pivot in A[p..r]
if i == k: return A[q] // pivot is the answer
else if i < k: return RANDOMIZED-SELECT(A, p, q-1, i)
else: return RANDOMIZED-SELECT(A, q+1, r, i-k)

Expected Time: O(n) — linear time selection

MODULE 2: GREEDY METHODS AND STRING MATCHING
Total Hours: 10 | Reference: CLRS Chapters 16, 21, 22, 23, 24, 32

2.1 Disjoint Sets (DS)

📌 Disjoint Set (Union-Find): A data structure that maintains a collection of disjoint dynamic sets, supporting
MAKE-SET, UNION, and FIND-SET operations.

Operations
• MAKE-SET(x): Creates a new set with element x as its only member
• UNION(x, y): Merges the sets containing x and y
• FIND-SET(x): Returns the representative (root) of the set containing x

Applications
• Kruskal's MST algorithm: Detecting cycles while adding edges
• Connected components in undirected graphs
• Network connectivity problems

Linked List Representation

Each set is stored as a linked list. The first element is the representative.
• MAKE-SET(x): O(1) — create new list with x
• FIND-SET(x): O(1) — follow pointer to list head
• UNION(x,y): O(n) — naively append one list to another
Weighted-union heuristic: Always append shorter list to longer. Amortized cost = O(m + n log n) for m operations
on n elements.

Disjoint Set Forests

Represent each set as a rooted tree. The root is the representative.

⚙ ALGORITHM: MAKE-SET, FIND-SET, UNION

MAKE-SET(x)
[Link] = x
[Link] = 0

FIND-SET(x) // with path compression

if x ≠ [Link]
[Link] = FIND-SET([Link])
return [Link]

UNION(x, y) // union by rank

 LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y) // union by rank

if [Link] > [Link]
[Link] = x
else
[Link] = y
if [Link] == [Link]
[Link] = [Link] + 1

Union by Rank + Path Compression

🔷 Inverse Ackermann Bound: With both union by rank AND path compression, m operations take O(m·α(n))
time, where α(n) is the inverse Ackermann function — effectively O(1) for all practical values of n (α(n) ≤ 4 for
n ≤ 10^(10^19728)).

2.2 Greedy Approach

📌 Greedy Algorithm: Makes the locally optimal choice at each step with the hope of finding a globally
optimal solution. Greedy algorithms do not reconsider choices once made.

Properties needed for a greedy algorithm to be correct:

• Greedy-choice property: A globally optimal solution can be obtained by making locally optimal (greedy)
choices
• Optimal substructure: An optimal solution to the problem contains optimal solutions to subproblems

Prim's Algorithm (MST)

📌 Minimum Spanning Tree (MST): A spanning tree of a connected, undirected, weighted graph whose total
edge weight is minimum.

Prim's starts with any vertex, and greedily grows the MST one edge at a time by always adding the minimum
weight edge that connects a vertex in the tree to a vertex outside.

⚙ ALGORITHM: PRIM'S MST ALGORITHM

MST-PRIM(G, w, r)
for each vertex u ∈ G.V
[Link] = ∞
u.π = NIL
[Link] = 0
Q = G.V // min-priority queue
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each vertex v ∈ [Link][u]
if v ∈ Q and w(u,v) < [Link]
v.π = u
[Link] = w(u,v) // decrease-key

Time: O((V + E) log V) using binary heap; O(E + V log V) using Fibonacci heap
Example: Graph with vertices {a,b,c,d,e,f,g,h,i} — start from vertex a. At each step, extract minimum key vertex
and add to MST.

Kruskal's Algorithm (MST)

Sort all edges by weight. Greedily add edges that don't create a cycle (using disjoint sets to detect cycles).

⚙ ALGORITHM: KRUSKAL'S MST ALGORITHM

MST-KRUSKAL(G, w)
A = ∅
for each vertex v ∈ G.V
MAKE-SET(v)
sort the edges of G.E by nondecreasing weight
for each edge (u,v) ∈ G.E in sorted order
if FIND-SET(u) ≠ FIND-SET(v)
A = A ∪ {(u,v)}
UNION(u, v)
return A

Time: O(E log E) = O(E log V) — dominated by sorting edges

Correctness: By the cut property — for any cut (S, V−S), the minimum weight edge crossing the cut belongs to
some MST.

Example: Graph with 4 vertices, edges: (a,b,4),(a,c,2),(b,c,1),(b,d,5),(c,d,8)

• Sorted edges: (b,c,1),(a,c,2),(a,b,4),(b,d,5),(c,d,8)
• Add (b,c): {b},{c} merge → {b,c}
• Add (a,c): {a},{b,c} merge → {a,b,c}
• Add (a,b): SKIP — a,b already connected
• Add (b,d): {a,b,c},{d} merge → MST = {(b,c),(a,c),(b,d)}, weight=8

Dijkstra's Shortest Path Algorithm

Single-source shortest paths in a graph with non-negative edge weights.

⚙ ALGORITHM: DIJKSTRA'S ALGORITHM

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = ∅
Q = G.V // min-priority queue keyed by d[v]
while Q ≠ ∅
u = EXTRACT-MIN(Q)
S = S ∪ {u}
for each vertex v ∈ [Link][u]
RELAX(u, v, w)

INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v ∈ G.V
 v.d = ∞
v.π = NIL
s.d = 0

RELAX(u, v, w)
if v.d > u.d + w(u,v)
v.d = u.d + w(u,v)
v.π = u

Time: O((V + E) log V) with binary heap; O(E + V log V) with Fibonacci heap
Limitation: Does NOT work with negative edge weights. Use Bellman-Ford instead.

Bellman-Ford Algorithm (SSSP)

Handles negative weight edges; detects negative weight cycles.

⚙ ALGORITHM: BELLMAN-FORD ALGORITHM

BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i = 1 to |G.V| - 1
for each edge (u,v) ∈ G.E
RELAX(u, v, w)
// Check for negative-weight cycles
for each edge (u,v) ∈ G.E
if v.d > u.d + w(u,v)
return FALSE // negative cycle detected
return TRUE

Time: O(VE)
Key Property: After |V|−1 iterations, all shortest paths are found (since no simple path has > |V|−1 edges)

Activity Selection Problem

Given n activities with start times sᵢ and finish times fᵢ, find the maximum-size subset of mutually compatible
activities.
📌 Compatible Activities: Activities i and j are compatible if [sᵢ, fᵢ) and [sⱼ, fⱼ) don't overlap.

⚙ ALGORITHM: GREEDY-ACTIVITY-SELECTOR
GREEDY-ACTIVITY-SELECTOR(s, f)
// Activities sorted by finish time: f₁ ≤ f₂ ≤ ... ≤ fₙ
n = [Link]
A = {a₁}
k = 1
for m = 2 to n
if s[m] ≥ f[k] // activity m starts after k finishes
A = A ∪ {aₘ}
k = m
return A
Time: O(n log n) — sorting dominates; O(n) after sorting
Greedy Choice: Always select the activity with the earliest finish time — leaves maximum time for remaining
activities.

Fractional Knapsack Problem

Given n items with weights wᵢ and values vᵢ, and a knapsack of capacity W, maximize value (fractions allowed).

⚙ ALGORITHM: FRACTIONAL-KNAPSACK
FRACTIONAL-KNAPSACK(W, items)
Sort items by value/weight ratio in decreasing order
total_value = 0
remaining = W
for each item i (in sorted order)
if w[i] ≤ remaining
take full item: total_value += v[i]
remaining -= w[i]
else
take fraction: total_value += v[i] * (remaining / w[i])
break
return total_value

Example: W=50, items: (60kg,10),(100kg,20),(120kg,30) → ratios: 6,5,4

• Take item1 fully (10kg, value 60), remaining=40
• Take item2 fully (20kg, value 100), remaining=20
• Take 2/3 of item3 (20kg, value 80), remaining=0
• Total value = 240
Time: O(n log n) — dominated by sorting
Note: 0/1 Knapsack (no fractions) cannot be solved greedily — needs DP!

Job Sequencing with Deadlines

Given n jobs with deadlines dᵢ and profits pᵢ, schedule jobs (each takes 1 unit) to maximize profit.

⚙ ALGORITHM: JOB-SEQUENCING-WITH-DEADLINES
JOB-SEQUENCING(jobs)
Sort jobs by profit in decreasing order
n = number of jobs
slot[1..n] = [false, false, ..., false]
result[] = []
for each job j (in sorted order by profit)
// Find latest available slot ≤ deadline
for t = min(n, d[j]) downto 1
if slot[t] == false
slot[t] = true
[Link](j)
 break
return result

Example: Jobs: J1(d=2,p=100), J2(d=1,p=19), J3(d=2,p=27), J4(d=1,p=25), J5(d=3,p=15)

• Sort by profit: J1(100), J3(27), J4(25), J2(19), J5(15)
• J1: assign slot 2 ✓
• J3: try slot 2 (taken) → slot 1 ✓
• J4: try slot 1 (taken) → no slot ✗
• Result: J3(slot1), J1(slot2) → profit=127
Time: O(n²) naive; O(n log n) with disjoint sets

2.3 String Matching Algorithms

📌 String Matching Problem: Given text T[1..n] and pattern P[1..m], find all occurrences of P in T. The
pattern occurs with shift s if T[s+1..s+m] = P[1..m].

Naïve String Matching

⚙ ALGORITHM: NAIVE-STRING-MATCHER
NAIVE-STRING-MATCHER(T, P)
n = [Link]
m = [Link]
for s = 0 to n - m
if P[1..m] == T[s+1..s+m]
print 'Pattern occurs with shift' s

Time: O((n−m+1)·m) — worst case: O(nm)

Example: T="aaaaab", P="aaaab" → checks every shift, takes O(nm) time

Rabin-Karp Algorithm
Uses hashing to quickly eliminate non-matching shifts. Computes a rolling hash of the text window and compares
with pattern hash.

📌 Rabin-Karp Hash: Uses modular arithmetic: p = (p₁·d^(m-1) + p₂·d^(m-2) + ... + pₘ) mod q, where d is
alphabet size and q is a prime.

⚙ ALGORITHM: RABIN-KARP-MATCHER
RABIN-KARP-MATCHER(T, P, d, q)
n = [Link]
m = [Link]
h = d^(m-1) mod q // highest-order digit multiplier
p = 0 // hash of pattern
t = 0 // hash of T[1..m]
// Preprocessing
for i = 1 to m
p = (d·p + P[i]) mod q
 t = (d·t + T[i]) mod q
// Matching
for s = 0 to n - m
if p == t
if P[1..m] == T[s+1..s+m]
print 'Pattern occurs with shift' s
if s < n - m
t = (d·(t - T[s+1]·h) + T[s+m+1]) mod q

Expected Time: O(n + m) — if few spurious hits (hash collisions)

Worst Case: O(nm) — all positions are spurious hits
Rolling Hash: t_new = (d·(t_old − T[s+1]·h) + T[s+m+1]) mod q — O(1) per shift

String Matching with Finite Automata

Build a finite automaton (DFA) from the pattern, then scan the text in O(n).

📌 Transition Function δ: δ(q, a) = σ(P[1..q]·a), where σ(x) is the length of the longest prefix of P that is also
a suffix of x.

⚙ ALGORITHM: COMPUTE-TRANSITION-FUNCTION
COMPUTE-TRANSITION-FUNCTION(P, Σ)
m = [Link]
for q = 0 to m
for each char a ∈ Σ
k = min(m+1, q+2)
repeat k = k - 1 until P[1..k] is suffix of P[1..q]·a
δ(q, a) = k
return δ

FINITE-AUTOMATON-MATCHER(T, δ, m)
n = [Link]
q = 0
for i = 1 to n
q = δ(q, T[i])
if q == m
print 'Pattern occurs with shift' i - m

Preprocessing: O(m³|Σ|) — computing transition function

Matching: O(n) — single scan of text

Knuth-Morris-Pratt (KMP) Algorithm

Avoids recomputing by precomputing a failure function (also called π function or partial match table).

📌 Failure Function π[q]: π[q] = length of the longest proper prefix of P[1..q] that is also a suffix of P[1..q].
Allows skipping characters on mismatch.
Example: P = 'ababaca'
• π[1]=0 (a): no proper prefix/suffix
• π[2]=0 (ab): 'a'≠'b'
• π[3]=1 (aba): 'a'='a' → π=1
• π[4]=2 (abab): 'ab'='ab' → π=2
• π[5]=3 (ababa): 'aba'='aba' → π=3
• π[6]=0 (ababac): no match
• π[7]=1 (ababaca): 'a'='a' → π=1
• π = [0, 0, 1, 2, 3, 0, 1]

⚙ ALGORITHM: KMP ALGORITHM

COMPUTE-PREFIX-FUNCTION(P)
m = [Link]
π[1] = 0
k = 0
for q = 2 to m
while k > 0 and P[k+1] ≠ P[q]
k = π[k]
if P[k+1] == P[q]
k = k + 1
π[q] = k
return π

KMP-MATCHER(T, P)
n = [Link]; m = [Link]
π = COMPUTE-PREFIX-FUNCTION(P)
q = 0 // number of chars matched
for i = 1 to n
while q > 0 and P[q+1] ≠ T[i]
q = π[q] // next state
if P[q+1] == T[i]
q = q + 1
if q == m
print 'Pattern at shift' i - m
q = π[q]

Preprocessing: O(m)
Matching: O(n)
Total: O(n + m) — much better than naïve O(nm)
Key Insight: When mismatch at P[q+1], we don't start over from P[1]; instead, jump to P[π[q]+1]

Algorithm Preprocessing Matching Total Notes

Naïve 0 O(nm) O(nm) Simple but

slow

Rabin-Karp O(m) O(n) O(n+m) avg Rolling hash

FA Matcher O(m|Σ|) O(n) O(n+m|Σ|) DFA-based

KMP O(m) O(n) O(n+m) Best
practical
MODULE 3: DYNAMIC PROGRAMMING AND MAXIMUM FLOW
Total Hours: 10 | Reference: CLRS Chapters 15, 25, 26

3.1 Dynamic Programming

📌 Dynamic Programming (DP): An algorithm design technique for optimization problems with optimal
substructure and overlapping subproblems. Solves each subproblem once and stores results in a table.

Two Approaches
• Top-down with memoization: Recursive solution with caching (memo table)
• Bottom-up: Fill table iteratively from smallest subproblems up

Longest Common Subsequence (LCS)

📌 LCS Problem: Given sequences X = <x₁,...,xₘ> and Y = <y₁,...,yₙ>, find the longest sequence that is a
subsequence of both.
Example: X = ABCBDAB, Y = BDCABA → LCS = BCBA (length 4)

Optimal Substructure:
• If xₘ = yₙ: LCS(X,Y) = LCS(Xₘ₋₁,Yₙ₋₁) + xₘ
• If xₘ ≠ yₙ: LCS(X,Y) = max(LCS(Xₘ₋₁,Y), LCS(X,Yₙ₋₁))

Recurrence:
⎧ 0 if i=0 or j=0
c[i,j]=⎨ c[i-1,j-1] + 1 if i,j>0 and xᵢ=yⱼ
⎩ max(c[i-1,j], c[i,j-1]) if i,j>0 and xᵢ≠yⱼ

⚙ ALGORITHM: LCS-LENGTH ALGORITHM

LCS-LENGTH(X, Y)
m = [Link]; n = [Link]
b[1..m, 1..n] and c[0..m, 0..n] = new tables
for i = 1 to m: c[i,0] = 0
for j = 0 to n: c[0,j] = 0
for i = 1 to m
for j = 1 to n
if X[i] == Y[j]
c[i,j] = c[i-1,j-1] + 1; b[i,j] = '↖'
else if c[i-1,j] ≥ c[i,j-1]
c[i,j] = c[i-1,j]; b[i,j] = '↑'
else
c[i,j] = c[i,j-1]; b[i,j] = '←'
return c and b

PRINT-LCS(b, X, i, j)
 if i == 0 or j == 0: return
if b[i,j] == '↖'
PRINT-LCS(b, X, i-1, j-1)
print X[i]
else if b[i,j] == '↑'
PRINT-LCS(b, X, i-1, j)
else
PRINT-LCS(b, X, i, j-1)

Time: Θ(mn)
Space: Θ(mn) — can be reduced to O(min(m,n)) if only length needed

Matrix Chain Multiplication

📌 Problem: Given matrices A₁, A₂, ..., Aₙ, find the optimal parenthesization that minimizes total scalar
multiplications.
Example: A₁(10×30), A₂(30×5), A₃(5×60):
• (A₁A₂)A₃: 10·30·5 + 10·5·60 = 1500 + 3000 = 4500
• A₁(A₂A₃): 30·5·60 + 10·30·60 = 9000 + 18000 = 27000
Optimal: First multiplication saves 22500 multiplications!

Recurrence: m[i,j] = minimum cost to compute AᵢAᵢ₊₁...Aⱼ

⎧ 0 if i = j
m[i,j]=⎨
⎩ min_{i≤k<j} { m[i,k] + m[k+1,j] + pᵢ₋₁·pₖ·pⱼ } if i < j

⚙ ALGORITHM: MATRIX-CHAIN-ORDER
MATRIX-CHAIN-ORDER(p)
n = [Link] - 1
m[1..n, 1..n] = new table (m[i,i]=0)
s[1..n-1, 2..n] = new table
for l = 2 to n // l = chain length
for i = 1 to n-l+1
j = i + l - 1
m[i,j] = ∞
for k = i to j-1
q = m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

Time: Θ(n³)
Space: Θ(n²)
Optimal Binary Search Trees
📌 OBST Problem: Given keys k₁<k₂<...<kₙ with search probabilities pᵢ and dummy key probabilities qᵢ, find
the BST minimizing expected search cost.
Expected cost of a BST T: E[search T] = Σᵢ(depth(kᵢ)+1)·pᵢ + Σᵢ(depth(dᵢ)+1)·qᵢ

e[i,j] = expected search cost of optimal BST for keys kᵢ...kⱼ

w[i,j] = Σₗ₌ᵢʲ pₗ + Σₗ₌ᵢ₋₁ʲ qₗ (total probability)

e[i,j] = min_{i≤r≤j} { e[i,r-1] + e[r+1,j] + w[i,j] }

⚙ ALGORITHM: OPTIMAL-BST
OPTIMAL-BST(p, q, n)
for i = 1 to n+1: e[i,i-1] = q[i-1]; w[i,i-1] = q[i-1]
for l = 1 to n
for i = 1 to n-l+1
j = i + l - 1
e[i,j] = ∞
w[i,j] = w[i,j-1] + p[j] + q[j]
for r = i to j
t = e[i,r-1] + e[r+1,j] + w[i,j]
if t < e[i,j]
e[i,j] = t; root[i,j] = r
return e and root
Time: Θ(n³)

0/1 Knapsack Problem

Given n items with weights wᵢ and values vᵢ, and capacity W, maximize value (items can't be split).

dp[i,w] = max value using items 1..i with capacity w

Base case: dp[0,w] = 0 for all w

Recurrence:
if w[i] > w: dp[i,w] = dp[i-1,w] (can't include item i)
else: dp[i,w] = max(dp[i-1,w], v[i] + dp[i-1, w-w[i]])

⚙ ALGORITHM: 0/1 KNAPSACK

KNAPSACK-01(w[], v[], n, W)
Create table dp[0..n][0..W]
for i = 0 to n
for w = 0 to W
if i == 0 or w == 0: dp[i][w] = 0
else if w[i] <= w
dp[i][w] = max(dp[i-1][w], v[i] + dp[i-1][w-w[i]])
else
dp[i][w] = dp[i-1][w]
return dp[n][W]
Time: Θ(nW) — pseudopolynomial
Space: O(nW); reducible to O(W)
Note: Unlike fractional knapsack, greedy fails here because items can't be split

3.2 All-Pairs Shortest Paths

📌 APSP Problem: Find shortest paths between every pair of vertices in a weighted graph.

Floyd-Warshall Algorithm
Uses DP. Let d⁽ᵏ⁾[i,j] = shortest path from i to j using only vertices {1,...,k} as intermediate vertices.

Recurrence:
d⁽⁰⁾[i,j] = w(i,j) [adjacency matrix, ∞ if no edge]
d⁽ᵏ⁾[i,j] = min(d⁽ᵏ⁻¹⁾[i,j], d⁽ᵏ⁻¹⁾[i,k] + d⁽ᵏ⁻¹⁾[k,j])

Final answer: d⁽ⁿ⁾[i,j] = shortest path for all i,j

⚙ ALGORITHM: FLOYD-WARSHALL
FLOYD-WARSHALL(W)
n = [Link]
D⁽⁰⁾ = W
for k = 1 to n
D⁽ᵏ⁾ = new n×n matrix
for i = 1 to n
for j = 1 to n
d⁽ᵏ⁾[i,j] = min(d⁽ᵏ⁻¹⁾[i,j], d⁽ᵏ⁻¹⁾[i,k] + d⁽ᵏ⁻¹⁾[k,j])
return D⁽ⁿ⁾

Time: Θ(V³)
Space: Θ(V²)
Handles: Negative weight edges (but not negative cycles). If d[i,i] < 0 after algorithm, negative cycle exists.

Shortest Paths and Matrix Multiplication

Alternative APSP approach: Lᵐ[i,j] = minimum weight of path from i to j with at most m edges.
L¹[i,j] = w(i,j)
Lᵐ[i,j] = min over k { L^(m-1)[i,k] + w(k,j) }
This is analogous to matrix multiplication! Compute L^(n-1) by repeated squaring → Θ(V³ log V).

Johnson's Algorithm (Sparse Graphs)

Combines Bellman-Ford and Dijkstra. Reweights edges to eliminate negatives, then runs Dijkstra from each
vertex.
⚙ ALGORITHM: JOHNSON'S ALGORITHM
JOHNSON(G, w)
// Add new vertex s with zero-weight edges to all V
G' = G with new vertex s and edges (s,v,0) for all v
if BELLMAN-FORD(G', w, s) == FALSE
'negative cycle detected'; return
// Reweighting: ĥ(v) = δ(s,v) from Bellman-Ford
for each edge (u,v) ∈ G.E
ŵ(u,v) = w(u,v) + h(u) - h(v) // ≥ 0 always
for each vertex u ∈ G.V
run DIJKSTRA(G, ŵ, u) → get Δ(u,v) for all v
for each vertex v: δ(u,v) = Δ(u,v) + h(v) - h(u)

Time: O(V²log V + VE) — better than Floyd-Warshall for sparse graphs (E << V²)

3.3 Flow Networks

📌 Flow Network: Directed graph G=(V,E) with source s, sink t, and capacity c(u,v)≥0 for each edge. A flow f
is a function satisfying capacity constraint and flow conservation.

Key Concepts
• Capacity constraint: 0 ≤ f(u,v) ≤ c(u,v) for all u,v
• Flow conservation: Σf(v,u) = Σf(u,v) for all u ≠ s,t (inflow = outflow)
• Value of flow: |f| = Σf(s,v) − Σf(v,s) (net flow out of source)
• Residual capacity: cₓ(u,v) = c(u,v) − f(u,v)
• Augmenting path: Simple path from s to t in residual graph with positive capacity

Ford-Fulkerson Method

⚙ ALGORITHM: FORD-FULKERSON METHOD

FORD-FULKERSON(G, s, t)
for each edge (u,v) ∈ G.E: f(u,v) = 0
while ∃ augmenting path p in residual Gₓ
cₓ(p) = min capacity along p
for each edge (u,v) in p
f(u,v) = f(u,v) + cₓ(p)
f(v,u) = f(v,u) - cₓ(p)

🔷 Max-Flow Min-Cut Theorem: The maximum value of a flow equals the minimum capacity of a cut
separating s from t. Three equivalent conditions: (1) f is max flow, (2) no augmenting path in residual, (3) |f| =
capacity of some cut.

Edmonds-Karp Algorithm
Ford-Fulkerson with BFS to find augmenting paths (shortest augmenting path).
Time: O(VE²) [tighter than Ford-Fulkerson's O(E·|f*|)]
Maximum Bipartite Matching
Given bipartite graph G=(L∪R, E), find maximum matching (max set of edges with no shared vertex).
Reduction to max flow:
• Add super-source s with edge to each vertex in L (capacity 1)
• Add super-sink t with edge from each vertex in R (capacity 1)
• Direct original edges from L to R (capacity 1)
• Run max flow → matching size = max flow value

Time: O(VE) using Ford-Fulkerson with unit capacities

MODULE 4: BACKTRACKING AND BRANCH-AND-BOUND
Total Hours: 8 | Reference: CLRS Chapter 34 + supplementary material

4.1 Backtracking
📌 Backtracking: A systematic method for searching the solution space. Builds solutions incrementally;
abandons a partial solution ('backtracks') as soon as it determines the partial solution cannot lead to a valid
complete solution.

General Backtracking Template:

⚙ ALGORITHM: GENERAL BACKTRACKING

BACKTRACK(state)
if IS-SOLUTION(state)
PROCESS-SOLUTION(state)
return
for each CHOICE in CANDIDATES(state)
if IS-VALID(state, CHOICE)
MAKE-CHOICE(state, CHOICE)
BACKTRACK(new_state)
UNDO-CHOICE(state, CHOICE) // backtrack

N-Queens Problem
Place N queens on an N×N chessboard such that no two queens attack each other (no shared row, column, or
diagonal).

⚙ ALGORITHM: N-QUEENS BACKTRACKING

N-QUEENS(n)
board[1..n] = 0 // board[i] = column of queen in row i
PLACE-QUEENS(board, 1, n)

PLACE-QUEENS(board, row, n)
if row > n
print solution; return
for col = 1 to n
if IS-SAFE(board, row, col)
board[row] = col
PLACE-QUEENS(board, row+1, n)
board[row] = 0 // backtrack

IS-SAFE(board, row, col)

for i = 1 to row-1
if board[i] == col: return false // same column
if |board[i] - col| == |i - row|: return false // diagonal
return true
Example (4-Queens): One solution is board = [2,4,1,3]:
• Row 1: Queen at col 2
• Row 2: Queen at col 4
• Row 3: Queen at col 1
• Row 4: Queen at col 3
For n=8, there are 92 solutions.
Time: O(n!) in worst case; backtracking prunes significantly

Sum of Subsets
Find all subsets of a given set of positive integers that sum to a target value M.

⚙ ALGORITHM: SUM-OF-SUBSETS BACKTRACKING

SUM-OF-SUBSETS(w[], s, k, n, M)
// w: weights, s: current sum, k: current index
// Sorted in nondecreasing order
include = true
for i = k+1 to n
if s + w[i] == M
print solution with w[i] included; include = false
if s + w[i] < M
x[i] = 1
SUM-OF-SUBSETS(w, s+w[i], i, n, M)
if include and (s + remaining_sum >= M) and (s + w[k] <= M)
x[k] = 0
SUM-OF-SUBSETS(w, s, k, n, M)

Pruning conditions:
• If s + w[k] > M: current element too large, skip (prune right subtree)
• If s + remaining elements < M: can't reach target, prune both subtrees

Graph Coloring
Assign colors to vertices of a graph such that no two adjacent vertices share the same color, using at most k
colors. (Chromatic number problem)

⚙ ALGORITHM: GRAPH COLORING BACKTRACKING

GRAPH-COLORING(G, k)
color[1..n] = 0
ASSIGN-COLOR(G, 1, k, color)

ASSIGN-COLOR(G, v, k, color)
if v > n: print color[]; return
for c = 1 to k
if IS-SAFE-COLOR(G, v, c, color)
color[v] = c
 ASSIGN-COLOR(G, v+1, k, color)
color[v] = 0 // backtrack

IS-SAFE-COLOR(G, v, c, color)
for each neighbor u of v
if color[u] == c: return false
return true

Note: The minimum k for which a valid coloring exists is the chromatic number χ(G). Determining χ(G) is NP-hard.

0/1 Knapsack via Backtracking

Systematically try including/excluding each item. Prune using upper bound.

⚙ ALGORITHM: KNAPSACK BACKTRACKING

KNAPSACK-BT(items, i, currentWeight, currentValue, W)
if currentWeight > W: return // prune: over capacity
if i == n
update best solution if currentValue > best; return
// Prune using upper bound (fractional relaxation)
upperBound = currentValue + FRACTIONAL(items, i, currentWeight, W)
if upperBound ≤ best: return // prune: can't improve
// Include item i
KNAPSACK-BT(items, i+1, currentWeight+w[i], currentValue+v[i], W)
// Exclude item i
KNAPSACK-BT(items, i+1, currentWeight, currentValue, W)

4.2 Branch-and-Bound
📌 Branch-and-Bound: An optimization technique that uses systematic enumeration (like backtracking) but
also maintains a bound on the best solution found so far to prune branches that cannot yield better solutions.

Key components:
• Branching: Divide the problem into subproblems
• Bounding: Compute an upper/lower bound for each subproblem
• Pruning: Eliminate subproblems whose bound is worse than current best solution

General B&B Framework

⚙ ALGORITHM: BRANCH-AND-BOUND GENERAL FRAMEWORK

BRANCH-AND-BOUND(problem)
Initialize priority queue PQ with root node
best = -∞ (for maximization)
while PQ not empty
node = EXTRACT-BEST(PQ) // by bound
if [Link] ≤ best: continue // prune
 if IS-LEAF(node)
best = max(best, [Link])
continue
for each CHILD of BRANCH(node)
[Link] = COMPUTE-BOUND(child)
if [Link] > best
[Link](child)
return best

0/1 Knapsack via B&B

Items sorted by decreasing value/weight ratio. Upper bound for a node = current value + fractional knapsack
value of remaining items with remaining capacity.

Example: W=10, items (sorted by v/w):

• Item 1: w=2, v=40, v/w=20
• Item 2: w=3.14, v=50, v/w=16
• Item 3: w=1.98, v=30, v/w=15
• Item 4: w=5, v=10, v/w=2
B&B Tree exploration: Start with (include 1) vs (exclude 1). Compute bound at each node. Prune when bound ≤
best known.

Travelling Salesman Problem (TSP)

Find the shortest Hamiltonian cycle in a complete weighted graph visiting all n cities exactly once.

⚙ ALGORITHM: TSP via BRANCH-AND-BOUND

TSP-BB(G, n)
// Compute lower bound: sum of (min edge + 2nd min edge)/2 for each vertex
lowerBound = Σᵢ (minEdge(i) + 2ndMinEdge(i)) / 2
Initialize PQ with partial tour containing only city 1
best = ∞
while PQ not empty
node = EXTRACT-MIN(PQ) // by lower bound
if [Link] ≥ best: continue // prune
if node is complete tour
best = [Link]; bestTour = [Link]
continue
for each unvisited city c
child = node + c
[Link] = COMPUTE-BOUND(child)
if [Link] < best
[Link](child)
return bestTour

Lower bound computation for partial tours: Use reduced cost matrix (subtract row/column minimums).
Worst Case: O(n!) — no polynomial guarantee, but B&B often much faster in practice
15-Puzzle Problem
Slide 15 tiles on a 4×4 board to reach goal state. Find minimum moves.
• State space: up to 15!/2 ≈ 10¹² reachable states
• B&B lower bound: Manhattan distance heuristic (sum of Manhattan distances of each tile to goal)
• IDA* (Iterative Deepening A*) is practically used

⚙ ALGORITHM: 15-PUZZLE via B&B

15-PUZZLE-BB(initialState, goalState)
bound = MANHATTAN-DISTANCE(initialState, goalState)
PQ = {(initialState, cost=0, bound)}
while PQ not empty
state = EXTRACT-MIN(PQ)
if state == goalState: return [Link]
for each MOVE in {LEFT, RIGHT, UP, DOWN}
newState = APPLY(state, MOVE)
g = [Link] + 1 // uniform move cost
h = MANHATTAN-DISTANCE(newState, goalState)
f = g + h // f = g + h
if f < best_found
[Link]((newState, cost=g, bound=f))
return NO-SOLUTION

Comparison: Backtracking vs Branch-and-Bound

Feature Backtracking Branch-and-Bound

Goal Find all/any solution Find optimal solution

Pruning Feasibility check Bound comparison

Search DFS Best-first (BFS/DFS)

Problems Constraint satisfaction Optimization

Examples N-Queens, Coloring TSP, Knapsack

Bound Not used Critical for efficiency

MODULE 5: APPROXIMATION AND NP-COMPLETENESS
Total Hours: 6 | Reference: CLRS Chapters 34, 35

5.1 NP-Completeness

Complexity Classes
📌 P (Polynomial Time): Class of decision problems solvable in polynomial time O(nᵏ) by a deterministic
Turing machine. Examples: Sorting, MST, Shortest Path.

📌 NP (Nondeterministic Polynomial): Class of decision problems verifiable in polynomial time. A certificate

(proposed solution) can be verified in O(nᵏ) time.

Key relationships:
• P ⊆ NP — every problem in P is in NP (just verify = solve)
• P = NP? — The million-dollar open question. Most believe P ≠ NP.
• NP-Hard: At least as hard as any problem in NP
• NP-Complete: In NP AND NP-Hard

Polynomial-Time Verification
📌 Verification Algorithm: For problem X with input I and certificate C: verify(I,C) runs in polynomial time and
returns TRUE iff C is a valid solution for I.
Example — Hamiltonian Cycle: Given graph G and certificate (a cycle), verify in O(V) that it visits all vertices
exactly once. So Ham-Cycle ∈ NP.

NP-Completeness and Reducibility

ₚPolynomial Reduction (≤ₚ): Problem A is polynomial-time reducible to B (A ≤ₚ B) if any instance of A can be
transformed to an instance of B in polynomial time, such that A's answer = B's answer.

Consequences of A ≤ₚ B:
• If B ∈ P then A ∈ P
• If A is NP-Hard and A ≤ₚ B, then B is NP-Hard

🔷 NP-Complete Definition: A problem X is NP-Complete if: (1) X ∈ NP, AND (2) every Y ∈ NP satisfies Y
≤ₚ X. Equivalently: (1) X ∈ NP, AND (2) some known NP-Complete problem Z ≤ₚ X.

Circuit Satisfiability (CIRCUIT-SAT)

Given a boolean combinational circuit, is there an assignment of inputs that makes output TRUE?
🔷 Cook-Levin Theorem: CIRCUIT-SAT is NP-Complete. Every problem in NP can be reduced to CIRCUIT-
SAT because any verification algorithm can be encoded as a circuit.
3-SAT (Satisfiability)
Given a boolean formula in CNF with exactly 3 literals per clause, is there a satisfying assignment?
Reduction: CIRCUIT-SAT ≤ₚ SAT ≤ₚ 3-SAT (each step in polynomial time).
• SAT: Given CNF formula, is it satisfiable?
• 3-SAT: More restricted form; still NP-Complete

Important NP-Complete Problems

1. Clique Problem
Given undirected graph G and integer k, does G contain a k-clique (complete subgraph of size k)?
Reduction: 3-SAT ≤ₚ CLIQUE
• For 3-SAT formula with k clauses, create graph G with 3k vertices (one per literal per clause)
• Connect vertices if they're in different clauses and not complementary
• Formula satisfiable ⟺ G has a k-clique

2. Vertex Cover
Given G and k, does G have a vertex cover of size ≤ k? (Set of vertices S such that every edge has at least one
endpoint in S)
Reduction: CLIQUE ≤ₚ VERTEX-COVER
• G has k-clique ⟺ complement G' has vertex cover of size n−k

3. Hamiltonian Cycle / TSP

Hamiltonian Cycle: Does graph G have a cycle visiting every vertex exactly once?
TSP Decision: Is there a tour of total weight ≤ k?
Reduction: VERTEX-COVER ≤ₚ HAM-CYCLE ≤ₚ TSP

4. Subset Sum
Given set S of integers and target t, is there a subset of S that sums to exactly t?
Reduction: 3-SAT ≤ₚ SUBSET-SUM

NP-Completeness Proof Structure

To prove problem X is NP-Complete:
1. Show X ∈ NP: Describe polynomial-time verification algorithm with certificate
2. Choose known NP-Complete problem Y
3. Construct polynomial reduction Y ≤ₚ X
4. Prove correctness: Y has YES answer ⟺ X has YES answer

Hierarchy of Complexity Classes:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
↑
NP-Complete
↑
 NP-Hard
(not in NP unless P=NP)

5.2 Approximation Algorithms

📌 Approximation Algorithm: An algorithm that runs in polynomial time and finds a solution whose value is
provably close to the optimal value. The approximation ratio ρ(n) satisfies: C/C* ≤ ρ(n) (for min) or C*/C ≤ ρ(n)
(for max), where C* is optimal.

Vertex Cover Approximation

Find a vertex cover (set of vertices covering all edges) of minimum size.
🔷 Optimal: : VERTEX-COVER is NP-Hard, so no polynomial exact algorithm exists (unless P=NP).

⚙ ALGORITHM: APPROX-VERTEX-COVER (2-approximation)

APPROX-VERTEX-COVER(G)
C = ∅
E' = G.E
while E' ≠ ∅
let (u,v) be any edge in E'
C = C ∪ {u, v}
// Remove all edges incident to u or v
E' = E' − {edges incident to u or v}
return C

🔷 2-Approximation Proof: Let A = set of edges chosen. A is a matching (no shared endpoints). Any cover
must include at least one endpoint of each edge in A → |C*| ≥ |A|. Algorithm outputs C with |C| = 2|A| ≤ 2|C*|.
Ratio: ρ(n) = 2

Travelling Salesman Problem Approximation

For metric TSP (satisfies triangle inequality):

⚙ ALGORITHM: APPROX-TSP-TOUR (2-approximation for metric TSP)

APPROX-TSP-TOUR(G, c)
r = any vertex of G
T = minimum spanning tree (Prim/Kruskal)
L = preorder walk of T (Euler tour, then shortcut)
return Hamiltonian cycle H visiting L in order

🔷 2-Approx Proof: Let H* be optimal tour. Removing any edge from H* gives spanning tree T* with weight ≤
c(H*). So c(T) ≤ c(T*) ≤ c(H*). Preorder walk W visits each edge of T twice: c(W)=2c(T)≤2c(H*). By triangle
inequality, shortcutting doesn't increase cost: c(H)≤c(W)≤2c(H*).
Ratio: ρ(n) = 2 | Note: For general TSP (no triangle ineq.), no constant approximation unless P=NP

Christofides Algorithm (Better TSP Approximation)

• Step 1: Compute MST T
 • Step 2: Find minimum-weight perfect matching M on odd-degree vertices of T
• Step 3: Form multigraph T ∪ M; find Eulerian circuit
• Step 4: Shortcut to get Hamiltonian cycle
Ratio: ρ(n) = 3/2 — best known polynomial approximation for metric TSP

Set Covering Problem

📌 Set Cover: Given universe U with |U|=n and collection of subsets F covering U, find smallest sub-collection
of F covering all of U.

⚙ ALGORITHM: GREEDY-SET-COVER (ln(n)-approximation)

GREEDY-SET-COVER(U, F)
C = ∅ // chosen subsets
while U not covered
S = argmax|S ∩ uncovered(U)| over S ∈ F // most uncovered
C = C ∪ {S}
U = U − S
return C

🔷 ln(n) Approximation Proof: If optimal cover has C* sets, greedy algorithm finds cover of size ≤ C* · (ln n +
1). This uses the harmonic series bound.
Ratio: ρ(n) = ln(n) + 1 ≈ O(log n)

Summary: Important NP-Complete Problems and Approximations

Problem NP-Hard? Best Approx Notes

Vertex Cover Yes 2-approx APPROX-VERTEX-

COVER

TSP (metric) Yes 1.5-approx Christofides

TSP (general) Yes None (unless P=NP) No const ratio

Set Cover Yes O(log n) Greedy optimal

Subset Sum Yes FPTAS ε-approx in polytime

Clique Yes None (inapprox) APX-hard

Graph Coloring Yes O(n/log n) Greedy heuristic

Quick Reference: Algorithm Complexities

Algorithm Best Average Worst Space

Insertion Sort Ω(n) Θ(n²) O(n²) O(1)

Selection Sort Ω(n²) Θ(n²) O(n²) O(1)

Merge Sort Ω(n log n) Θ(n log n) O(n log n) O(n)

Quick Sort Ω(n log n) Θ(n log n) O(n²) O(log n)

Prim's MST — — O(E log V) O(V)

Kruskal's MST — — O(E log V) O(V)

Dijkstra — — O(E log V) O(V)

Bellman-Ford — — O(VE) O(V)

Floyd-Warshall — — O(V³) O(V²)

Johnson's — — O(VE+V²logV) O(V²)

KMP — — O(n+m) O(m)

Rabin-Karp — — O(nm) O(1)

LCS (DP) — — O(mn) O(mn)

0/1 Knapsack — — O(nW) O(nW)

Ford-Fulkerson — — O(E|f*|) O(V)

Edmonds-Karp — — O(VE²) O(V)