Essential Algorithms and Complexity Theory Reference

Posted on Mar 10, 2026 in Computer Engineering

Matrix Chain Multiplication

1. Begin
2. If N = 1: Print “Cost = 0” and Exit.
3. i = 0 (Start index for splitting).
4. Repeat steps 5 & 6 while i < N – 1:
5. If i < N – 1:
   • Cost1 = MCM(P, i + 1)
   • Cost2 = MCM(P + i + 1, N – i – 1)
   • CurrentCost = Cost1 + Cost2 + (P[0] * P[i + 1] * P[N])
   • If i = 0: MinCost = CurrentCost; Else if CurrentCost < MinCost: MinCost = CurrentCost
   • i = i + 1
6. Print “Minimum cost = “, MinCost
7. Exit

Job Sequencing with Deadline (Greedy)

1. Start
2. Sort all jobs in descending order of profit.
3. Find MaxDeadline among all jobs.
4. Create array Slot[0…MaxDeadline-1], initialize to -1.
5. Set TotalProfit = 0.
6. For i = 0 to N-1:
   • Set slot = J[i].deadline – 1
   • While slot >= 0:
     • If Slot[slot] == -1: Slot[slot] = J[i].id; TotalProfit += J[i].profit; Break
     • Else: slot = slot – 1
7. Print scheduled jobs and TotalProfit.
8. Stop

Graph Coloring

1. Begin
2. i = 0
3. Create Color array, set all Color[i] = -1.
4. Repeat steps 5 & 6 while i < N:
5. (i) Create Available array, set all Available[c] = 1.
   (ii) For j = 0 to N-1: If G[i][j] = 1 AND Color[j] ≠ -1: Available[Color[j]] = 0.
   (iii) c = 0.
   (iv) While Available[c] = 0: c = c + 1.
   (v) Color[i] = c.
   (vi) Print “Vertex “, i, ” assigned color “, c.
6. i = i + 1
7. Exit

Kruskal’s Algorithm

1. Start
2. Sort all edges in ascending order of weight.
3. Initialize MST as empty set; TotalCost = 0.
4. Make each vertex a separate set (Disjoint Set).
5. For each edge (u, v) in sorted order: If Find(u) ≠ Find(v): Add edge to MST; TotalCost += weight; Union(u, v).
6. Repeat until MST contains (V − 1) edges.
7. Print MST edges and TotalCost.
8. Stop

Prim’s Algorithm

1. Start
2. Choose starting vertex.
3. Initialize Selected[] array; mark start as selected; TotalCost = 0.
4. Repeat until (V − 1) edges are selected:
   • Find minimum weight edge (u, v) where u is in Selected and v is not.
   • Add edge to MST; mark v as Selected; TotalCost += weight.
5. Print MST edges and TotalCost.
6. Stop

N-Queen Problem

1. Start
2. Create Board[0…N-1], initialize to -1.
3. i = 0.
4. While i >= 0 and i < N:
   • (a) Set col = Board[i] + 1.
   • (b) While col < N and NOT IsSafe(Board, i, col): col = col + 1.
   • (c) If col < N: Board[i] = col; i = i + 1.
   • (d) Else: Board[i] = -1; i = i – 1 (Backtrack).
5. If i == N: Print queen positions.
6. Stop

TSP Using Dynamic Programming

1. Begin
2. i = 0 (Start vertex 0).
3. Create DP array[2^N][N], set all to -1.
4. Mask = 1.
5. Repeat steps 6 & 7 while i < N:
6. If DP[Mask][i] = -1:
   • If Mask = (2^N – 1): DP[Mask][i] = G[i][0]; Go to step 8.
   • MinCost = ∞.
   • For j = 0 to N-1: If (Mask AND (1 << j)) = 0: Cost = G[i][j] + TSP(G, N, j, Mask OR (1 << j)); If Cost < MinCost: MinCost = Cost.
   • DP[Mask][i] = MinCost.
7. i = i + 1
8. Print “Minimum distance = “, DP[1][0].
9. Exit

KMP Algorithm

Part 1: Construct LPS Array

ComputeLPS(P, m): Set lps[0]=0, len=0, i=1. While i < m: If P[i] == P[len]: len++, lps[i]=len, i++. Else: If len ≠ 0: len = lps[len-1]. Else: lps[i]=0, i++.

Part 2: Pattern Matching

KMPSearch(T, P): Compute LPS. Set i=0, j=0. While i < n: If P[j] == T[i]: i++, j++. If j == m: Print match, j = lps[j-1]. Else if i < n and P[j] ≠ T[i]: If j ≠ 0: j = lps[j-1]. Else: i++.

Sorting Algorithms

Merge Sort

Divide and conquer approach: Split array into halves, recursively sort, and merge sorted subarrays.

Quick Sort

Partitioning approach: Select a pivot, rearrange elements such that smaller elements are on the left and larger on the right, then recurse.

Shortest Path Algorithms

• Floyd-Warshall: All-pairs shortest path using dynamic programming.
• Dijkstra’s: Single-source shortest path for non-negative weights.
• Bellman-Ford: Single-source shortest path; handles negative weights and detects negative cycles.

Backtracking vs. Branch and Bound

Vertex Cover NP-Completeness

A Vertex Cover is a subset of vertices C such that every edge has at least one endpoint in C. It is proven NP-Complete by reducing the CLIQUE problem to it using the complement graph G’, where a clique of size k in G corresponds to a vertex cover of size |V| – k in G’.