U1
Recurrence Relations
Master Method
Recurrence Relation.pdf
A "cookbook" method for solving T(n) = aT(n/b) + f(n).
- Case 1: If log_b(a) > k, then T(n) = Θ(n^{log_b(a)})
- Case 2: If log_b(a) == k, then T(n) = Θ(n^k log^{p+1} n)
- Case 3: If log_b(a) < k, then T(n) = Θ(f(n))
Time: O(Depends)
Space: O(log n)
U2
Divide and Conquer
Merge Sort
MergeSort.pdf
Stable, O(n log n) sorting algorithm.
// Merge(A, left, mid, right)
function mergeSort(A, p, r) {
if (p < r) {
q = floor((p+r)/2);
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
function mergeSort(A, p, r) {
if (p < r) {
q = floor((p+r)/2);
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
Peak Index in Mountain Array
Peak Index Mountain Array.pdf
Finding index i such that A[0] < ... < A[i] > ... > A[n-1].
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] < arr[mid+1]) left = mid + 1;
else right = mid;
}
mid = (left + right) / 2;
if (arr[mid] < arr[mid+1]) left = mid + 1;
else right = mid;
}
Time: O(log n)
Maximum Subarray Sum (D&C)
MaxSubarraySum.pdf
Dividing array into left/right and checking the cross-sum.
- maxLeft = solve(left_half)
- maxRight = solve(right_half)
- maxCross = cross_sum(left, mid, right)
- return max(maxLeft, maxRight, maxCross)
Time: O(n log n)
U3
Greedy Algorithms
Minimum Platforms Problem
Minimum Platforms Problem.pdf
Sorting arrival and departure times separately to find max simultaneous trains.
sort(arr); sort(dep);
while (i < n && j < n) {
if (arr[i] <= dep[j]) { platforms++; i++; }
else { platforms--; j++; }
res = max(res, platforms);
}
while (i < n && j < n) {
if (arr[i] <= dep[j]) { platforms++; i++; }
else { platforms--; j++; }
res = max(res, platforms);
}
Time: O(n log n)
Huffman Coding
Huffman (2).pdf
Prefix coding for data compression. Uses a priority queue to build a tree from frequencies.
U4
Dynamic Programming
Basic Theory & Explanation
Optimization over recursion. Breaks down a complex problem into simpler subproblems, solving each subproblem just once, and storing their solutions.
- Optimal Substructure: Optimal solution of the problem relies on optimal solutions of its subproblems.
- Overlapping Subproblems: Subproblems are evaluated many times.
Longest Common Subsequence (LCS)
Find the longest subsequence present in both strings.
// dp[i][j] stores LCS length of S1[0..i-1] and S2[0..j-1]
function LCS(S1, S2) {
for i = 0 to n:
for j = 0 to m:
if (i == 0 || j == 0) dp[i][j] = 0;
else if (S1[i-1] == S2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
return dp[n][m];
}
function LCS(S1, S2) {
for i = 0 to n:
for j = 0 to m:
if (i == 0 || j == 0) dp[i][j] = 0;
else if (S1[i-1] == S2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
return dp[n][m];
}
Time: O(n*m)Space: O(n*m)
Matrix Chain Multiplication (MCM)
Find the most efficient way to multiply a given sequence of matrices.
// m[i][j] is min scalar multiplications to compute A_i..A_j
for L = 2 to n: // Chain length
for i = 1 to n - L + 1:
j = i + L - 1;
m[i][j] = infinity;
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;
for L = 2 to n: // Chain length
for i = 1 to n - L + 1:
j = i + L - 1;
m[i][j] = infinity;
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;
Time: O(n^3)Space: O(n^2)
U5
Backtracking
Basic Theory
Algorithmic technique for solving problems recursively by building a solution incrementally, one piece at a time, removing those solutions that fail to satisfy constraints at any point.
N-Queens Problem
Place N queens on an NxN chessboard so that no two queens attack each other.
function solveNQueens(board, col) {
if (col >= N) return true; // Base case: all placed
for (row = 0 to N-1) {
if (isSafe(board, row, col)) {
board[row][col] = 1; // Place queen
if (solveNQueens(board, col + 1)) return true;
board[row][col] = 0; // Backtrack
}
}
return false;
}
if (col >= N) return true; // Base case: all placed
for (row = 0 to N-1) {
if (isSafe(board, row, col)) {
board[row][col] = 1; // Place queen
if (solveNQueens(board, col + 1)) return true;
board[row][col] = 0; // Backtrack
}
}
return false;
}
Time: O(N!)Space: O(N)
Hamiltonian Cycle
Find a cycle in an undirected graph visiting every vertex exactly once and returning to the start.
function hamCycleUtil(graph, path, pos) {
if (pos == V) {
// Check edge from last to first
return graph[path[pos-1]][path[0]] == 1;
}
for (v = 1 to V-1) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1)) return true;
path[pos] = -1; // Backtrack
}
}
return false;
}
if (pos == V) {
// Check edge from last to first
return graph[path[pos-1]][path[0]] == 1;
}
for (v = 1 to V-1) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1)) return true;
path[pos] = -1; // Backtrack
}
}
return false;
}
Time: O(N!)Space: O(N)
Farmer Problem (Wolf, Goat, Cabbage)
Transport a wolf, goat, and cabbage across a river. Restrictions: Wolf eats goat, goat eats cabbage if alone.
// State representation: (Farmer, Wolf, Goat, Cabbage) in {0,1}
function solve(state, visited, path) {
if (state == (1,1,1,1)) return true;
for (next_state in getValidMoves(state)) {
if (next_state not in visited) {
visited.add(next_state);
path.push(next_state);
if (solve(next_state, visited, path)) return true;
path.pop(); // Backtrack
visited.remove(next_state);
}
}
return false;
}
function solve(state, visited, path) {
if (state == (1,1,1,1)) return true;
for (next_state in getValidMoves(state)) {
if (next_state not in visited) {
visited.add(next_state);
path.push(next_state);
if (solve(next_state, visited, path)) return true;
path.pop(); // Backtrack
visited.remove(next_state);
}
}
return false;
}
U8
Branch and Bound
Theory
Optimization technique for finding optimal solutions. It systematically explores branches of a search tree and maintains a "bound" on the optimal solution. If a branch's bound is worse than the best known solution, it is pruned.
0/1 Knapsack (Branch & Bound)
Use a Priority Queue to explore nodes with the best potential profit upper bound.
// Sort items by value/weight ratio
PQ.push(dummy_node)
maxProfit = 0
while (!PQ.empty()) {
node = PQ.pop();
if (node.bound > maxProfit) {
// Branch 1: Include item
child1 = createNode(include);
if (child1.weight <= W && child1.profit > maxProfit) maxProfit = child1.profit;
if (child1.bound > maxProfit) PQ.push(child1);
// Branch 2: Exclude item
child2 = createNode(exclude);
if (child2.bound > maxProfit) PQ.push(child2);
}
}
PQ.push(dummy_node)
maxProfit = 0
while (!PQ.empty()) {
node = PQ.pop();
if (node.bound > maxProfit) {
// Branch 1: Include item
child1 = createNode(include);
if (child1.weight <= W && child1.profit > maxProfit) maxProfit = child1.profit;
if (child1.bound > maxProfit) PQ.push(child1);
// Branch 2: Exclude item
child2 = createNode(exclude);
if (child2.bound > maxProfit) PQ.push(child2);
}
}
U6
Graph Theory
Topological Sort (Kahn's Algorithm)
Finds a linear ordering of vertices in a Directed Acyclic Graph (DAG).
function KahnTopologicalSort(Graph) {
inDegree = array of 0s;
for each u in Graph: for each v in Graph.adj[u]: inDegree[v]++;
Q = empty queue;
for i = 0 to V-1: if (inDegree[i] == 0) Q.push(i);
count = 0; topOrder = empty list;
while (!Q.empty()) {
u = Q.pop(); topOrder.push(u);
for each v in Graph.adj[u] {
inDegree[v]--;
if (inDegree[v] == 0) Q.push(v);
}
count++;
}
if (count != V) return "Cycle Exists!";
return topOrder;
}
inDegree = array of 0s;
for each u in Graph: for each v in Graph.adj[u]: inDegree[v]++;
Q = empty queue;
for i = 0 to V-1: if (inDegree[i] == 0) Q.push(i);
count = 0; topOrder = empty list;
while (!Q.empty()) {
u = Q.pop(); topOrder.push(u);
for each v in Graph.adj[u] {
inDegree[v]--;
if (inDegree[v] == 0) Q.push(v);
}
count++;
}
if (count != V) return "Cycle Exists!";
return topOrder;
}
Time: O(V + E)
Strongly Connected Components (Tarjan's)
Finds SCCs in a directed graph using a single DFS.
function SCCUtil(u, disc, low, stack, inStack) {
disc[u] = low[u] = ++time;
stack.push(u); inStack[u] = true;
for each v in adj[u] {
if (disc[v] == -1) { // unvisited
SCCUtil(v, disc, low, stack, inStack);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) { // Back edge
low[u] = min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) { // Head of SCC
while(stack.top() != u) {
v = stack.pop(); inStack[v] = false; print v;
}
v = stack.pop(); inStack[v] = false; print v;
}
}
disc[u] = low[u] = ++time;
stack.push(u); inStack[u] = true;
for each v in adj[u] {
if (disc[v] == -1) { // unvisited
SCCUtil(v, disc, low, stack, inStack);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) { // Back edge
low[u] = min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) { // Head of SCC
while(stack.top() != u) {
v = stack.pop(); inStack[v] = false; print v;
}
v = stack.pop(); inStack[v] = false; print v;
}
}
Time: O(V + E)
Max-Flow Min-Cut (Ford-Fulkerson)
Finds maximum flow in a network. Min-Cut capacity equals Max-Flow.
function FordFulkerson(graph, source, sink) {
max_flow = 0;
rGraph = copy(graph); // Residual graph
while (BFS(rGraph, source, sink, parent)) {
path_flow = infinity;
s = sink;
while (s != source) {
path_flow = min(path_flow, rGraph[parent[s]][s]);
s = parent[s];
}
v = sink;
while (v != source) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
v = parent[v];
}
max_flow += path_flow;
}
return max_flow;
}
max_flow = 0;
rGraph = copy(graph); // Residual graph
while (BFS(rGraph, source, sink, parent)) {
path_flow = infinity;
s = sink;
while (s != source) {
path_flow = min(path_flow, rGraph[parent[s]][s]);
s = parent[s];
}
v = sink;
while (v != source) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
v = parent[v];
}
max_flow += path_flow;
}
return max_flow;
}
Time: O(E * max_flow)
U7
String Programs
Rabin-Karp Algorithm
Uses hashing to find pattern matches. Rolling hash avoids recomputing hash from scratch.
function RabinKarp(txt, pat, q) {
d = 256; p = 0; t = 0; h = 1;
for (i = 0 to M-2) h = (h * d) % q;
for (i = 0 to M-1) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0 to N-M) {
if (p == t) {
if (txt[i..i+M-1] == pat) print "Found at index " + i;
}
if (i < N-M) {
t = (d * (t - txt[i]*h) + txt[i+M]) % q;
if (t < 0) t = t + q;
}
}
}
d = 256; p = 0; t = 0; h = 1;
for (i = 0 to M-2) h = (h * d) % q;
for (i = 0 to M-1) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0 to N-M) {
if (p == t) {
if (txt[i..i+M-1] == pat) print "Found at index " + i;
}
if (i < N-M) {
t = (d * (t - txt[i]*h) + txt[i+M]) % q;
if (t < 0) t = t + q;
}
}
}
Time: Average O(N+M), Worst O(N*M)
Knuth-Morris-Pratt (KMP)
Avoids re-evaluating characters by using an LPS (Longest Prefix Suffix) array.
function computeLPSArray(pat, M, lps) {
len = 0; i = 1; lps[0] = 0;
while (i < M) {
if (pat[i] == pat[len]) { len++; lps[i] = len; i++; }
else {
if (len != 0) len = lps[len-1];
else { lps[i] = 0; i++; }
}
}
}
function KMPSearch(pat, txt) {
computeLPSArray(pat, M, lps);
i = 0; j = 0;
while (i < N) {
if (pat[j] == txt[i]) { j++; i++; }
if (j == M) { print "Found at " + (i-j); j = lps[j-1]; }
else if (i < N && pat[j] != txt[i]) {
if (j != 0) j = lps[j-1];
else i++;
}
}
}
len = 0; i = 1; lps[0] = 0;
while (i < M) {
if (pat[i] == pat[len]) { len++; lps[i] = len; i++; }
else {
if (len != 0) len = lps[len-1];
else { lps[i] = 0; i++; }
}
}
}
function KMPSearch(pat, txt) {
computeLPSArray(pat, M, lps);
i = 0; j = 0;
while (i < N) {
if (pat[j] == txt[i]) { j++; i++; }
if (j == M) { print "Found at " + (i-j); j = lps[j-1]; }
else if (i < N && pat[j] != txt[i]) {
if (j != 0) j = lps[j-1];
else i++;
}
}
}
Time: O(N+M)
U9
Complexity Classes & Randomized Algorithms
NP-Complete and NP-Hard Problems
- P: Solvable in polynomial time.
- NP: Solutions can be verified in polynomial time.
- NP-Hard: As hard as the hardest problems in NP. Not necessarily in NP.
- NP-Complete: Problems that are both NP-Hard and in NP. If any NPC problem can be solved in P, then P=NP.
Las Vegas Algorithm (Randomized QuickSort)
Las Vegas: A randomized algorithm that always produces the correct result but has a random running time.
function RandomizedQuickSort(arr, low, high) {
if (low < high) {
randomIndex = random(low, high);
swap(arr[randomIndex], arr[high]);
pi = partition(arr, low, high);
RandomizedQuickSort(arr, low, pi - 1);
RandomizedQuickSort(arr, pi + 1, high);
}
}
if (low < high) {
randomIndex = random(low, high);
swap(arr[randomIndex], arr[high]);
pi = partition(arr, low, high);
RandomizedQuickSort(arr, low, pi - 1);
RandomizedQuickSort(arr, pi + 1, high);
}
}
Expected Time: O(N log N)
Monte Carlo Algorithm (Karger's Min Cut)
Monte Carlo: Always runs in fixed polynomial time but has a probability of producing an incorrect result.
function KargerMinCut(graph) {
V = graph.vertices;
while (V > 2) {
edge = getRandomEdge(graph);
contractEdge(graph, edge.u, edge.v);
V--;
}
return countEdges(graph);
}
V = graph.vertices;
while (V > 2) {
edge = getRandomEdge(graph);
contractEdge(graph, edge.u, edge.v);
V--;
}
return countEdges(graph);
}
Time: O(E) per trial
VS
0/1 Knapsack: Complete Comparison
Comparison of all variants
A comprehensive overview of solving 0/1 Knapsack (Find max value within Weight W) using 4 different algorithmic paradigms.
| Method | Approach | Time Complexity | Space Complexity | Optimality |
|---|---|---|---|---|
| Greedy | Sort by Value/Weight ratio. Pick highest ratio items first until full. | O(N log N) | O(1) | NOT Optimal for 0/1 |
| DP (Tabulation) | Build a 2D table dp[i][w] to store max profit for item i at weight w. | O(N * W) | O(N * W) | Optimal (Pseudo-poly) |
| Backtracking | Recursively explore all 2^N subsets (Include / Exclude each item). | O(2^N) | O(N) stack | Optimal |
| Branch & Bound | Use Priority Queue and compute upper bounds. Prunes bad branches. | O(2^N) Worst, avg faster | O(2^N) Queue space | Optimal |
Summary: Use DP when capacity W is relatively small. Use Branch & Bound for larger capacities where DP table would exceed memory, as B&B prunes the search space efficiently.