Algorithm Formulas & Reference - DSA Study Platform

Quick Navigation by Task

Shortest Path Problems
Graph Traversal & Ordering
Minimum Spanning Tree
Greedy Optimization
Dynamic Programming Optimization
Network Flow
Divide and Conquer

TASK: Finding Shortest Paths

Algorithms for finding shortest paths from source to other vertices

BFS (Breadth-First Search)

For unweighted graphs

Time: O(V + E)

Space: O(V)

🎯 Decision Rule (Formulaic):

At each step: CHOOSE: Next vertex u from front of queue FOR EACH: unvisited neighbor v of u ENQUEUE(v) d[v] = d[u] + 1

Why this rule? Queue ensures FIFO → explores vertices level by level → guarantees shortest path in unweighted graphs

When to Use:

Finding shortest path in unweighted graphs
Finding minimum number of edges between vertices
Level-order traversal

Distance Formula:

d[v] = d[u] + 1 where u is parent of v in BFS tree Base case: d[s] = 0 for source s

Variables:

Variable	Meaning
V	Number of vertices
E	Number of edges
d[v]	Distance (number of edges) from source to v
Q	Queue of vertices to visit

Dijkstra's Algorithm

For weighted graphs with non-negative weights

Time: O((V+E) log V)

Space: O(V)

🎯 Decision Rule (Formulaic):

At each step: CHOOSE: u = argmin{d[v] : v not yet finalized} (vertex with minimum distance estimate) FOR EACH: neighbor v of u IF d[v] > d[u] + w(u,v): ← RELAXATION d[v] = d[u] + w(u,v) π[v] = u

Why this rule? Greedy choice of minimum distance is safe because all weights are non-negative → cannot find shorter path later

When to Use:

Finding shortest paths in weighted graphs
ONLY when all edge weights are non-negative
Single-source shortest paths (from one source to all vertices)
GPS navigation, network routing

Relaxation Formula (Core Decision):

RELAX(u, v, w): if d[v] > d[u] + w(u,v): d[v] = d[u] + w(u,v) π[v] = u decreaseKey(Q, v, d[v]) // update priority queue

Variables:

Variable	Meaning
d[v]	Current shortest distance estimate from source to v
π[v]	Predecessor of v in shortest path tree
w(u,v)	Weight of edge from u to v (must be ≥ 0)
Q	Min-priority queue keyed by d[v]

Complete Algorithm:

INITIALIZE: d[s] = 0 d[v] = ∞ for all v ≠ s π[v] = NIL for all v Q = all vertices with key d[v] WHILE Q ≠ ∅: u = extractMin(Q) FOR EACH neighbor v of u: RELAX(u, v, w)

TASK: Graph Traversal & Ordering

Algorithms for exploring graphs and establishing orderings

DFS (Depth-First Search)

For deep exploration and cycle detection

Time: O(V + E)

Space: O(V)

🎯 Decision Rule (Formulaic):

At each step: CHOOSE: First unvisited neighbor v of current vertex u IF no unvisited neighbors: BACKTRACK to parent Recursively: DFS(v)

Why this rule? Stack/recursion ensures LIFO → explores as deep as possible before backtracking

When to Use:

Topological sorting (for DAGs)
Finding strongly connected components
Cycle detection
Path finding (when all paths needed, not just shortest)

Timestamps:

d[v] = discovery time (when first visited) f[v] = finish time (when all descendants explored) Property: d[u] < d[v] < f[v] < f[u] iff v is descendant of u

Topological Sort

For ordering dependent tasks (DAGs only)

Time: O(V + E)

Space: O(V)

🎯 Decision Rule (Formulaic):

At each step: WHEN vertex v finishes in DFS (all descendants explored): PUSH v onto stack S FINAL ORDER: Pop all vertices from S

Why this rule? Vertices with later finish times have no outgoing edges to vertices with earlier finish times → correct topological order

When to Use:

Scheduling tasks with dependencies
Course prerequisite ordering
ONLY works on DAGs (Directed Acyclic Graphs)

Correctness Property:

For any edge (u,v): f[u] > f[v] Therefore, u appears before v in topological order

Strongly Connected Components (Kosaraju's)

For finding maximal strongly connected subgraphs

Time: O(V + E)

Space: O(V)

🎯 Decision Rule (Formulaic):

Pass 1: DFS on G, compute finish times f[v] Pass 2: DFS on G^T in decreasing order of f[v] CHOOSE: In Pass 2, start new DFS from vertex with max f[v] among unvisited vertices Each DFS tree in Pass 2 = one SCC

Algorithm:

Run DFS on G, compute f[v] for all v
Compute G^T (transpose - reverse all edges)
Run DFS on G^T, processing vertices in decreasing f[v] order
Each DFS tree = one SCC

TASK: Minimum Spanning Tree

Algorithms for connecting all vertices with minimum total edge weight

Kruskal's Algorithm (Edge-Based MST)

Time: O(E log E)

Space: O(V)

🎯 Decision Rule (Formulaic):

SORT all edges by weight: w(e₁) ≤ w(e₂) ≤ ... ≤ w(eₘ) FOR EACH edge (u,v) in sorted order: CHOOSE (u,v) IF Find(u) ≠ Find(v) (doesn't create cycle) IF chosen: A = A ∪ {(u,v)} Union(u, v) STOP when |A| = V - 1

Why this rule? Minimum weight edge that doesn't create cycle is always safe to add (Cut Property)

When to Use Kruskal's vs Prim's:

Kruskal's better for sparse graphs (few edges)
Kruskal's good when edges already sorted
Easier to parallelize than Prim's

MST Properties:

Has exactly V-1 edges
Connects all vertices (spanning)
No cycles (tree)
Total weight = Σ w(e) is minimum

Prim's Algorithm (Vertex-Based MST)

Time: O((V+E) log V)

Space: O(V)

🎯 Decision Rule (Formulaic):

At each step: CHOOSE: u = argmin{key[v] : v ∉ MST} (vertex not in MST with minimum edge to MST) ADD u to MST FOR EACH neighbor v of u (v not in MST): IF w(u,v) < key[v]: key[v] = w(u,v) π[v] = u

Why this rule? Minimum weight edge crossing cut between MST and non-MST vertices is always safe (Cut Property)

When to Use Prim's vs Kruskal's:

Prim's better for dense graphs (many edges)
Prim's better when using adjacency matrix
Similar to Dijkstra's in structure

Variables:

Variable	Meaning
key[v]	Minimum weight of edge connecting v to MST
π[v]	Parent of v in MST
Q	Min-priority queue of vertices not yet in MST

TASK: Greedy Optimization Problems

Problems where local optimal choices lead to global optimum

Activity Selection

Maximize number of non-overlapping activities

Time: O(n log n)

Space: O(1)

🎯 Decision Rule (Formulaic):

SORT activities by finish time: f[1] ≤ f[2] ≤ ... ≤ f[n] CHOOSE: a[1] (earliest finish time) FOR i = 2 to n: CHOOSE a[i] IF s[i] ≥ f[k] (start time ≥ last selected finish time) IF chosen: k = i

Why this rule? Activity with earliest finish time leaves maximum room for remaining activities

Variables:

Variable	Meaning
s[i]	Start time of activity i
f[i]	Finish time of activity i
k	Index of last selected activity

Huffman Coding

Optimal prefix-free binary encoding

Time: O(n log n)

Space: O(n)

🎯 Decision Rule (Formulaic):

WHILE |Q| > 1: CHOOSE: x = extractMin(Q) (lowest frequency) CHOOSE: y = extractMin(Q) (second lowest frequency) CREATE: z with freq[z] = freq[x] + freq[y] INSERT: z into Q MAKE: x and y children of z

Why this rule? Merging lowest frequency nodes minimizes total cost Σ f[c] · depth[c]

Cost Formula:

Cost(T) = Σ freq[c] · depth[c] where: - freq[c] = frequency of character c - depth[c] = depth in tree = code length

TASK: Dynamic Programming Optimization

Problems with overlapping subproblems and optimal substructure

DP General Framework

Top-Down vs Bottom-Up:

Approach	Method	When to Use
Top-Down (Memoization)	Recursive with cache	When not all subproblems needed; easier to write
Bottom-Up (Tabulation)	Iterative table filling	When all subproblems needed; better performance

Rod Cutting

Maximize revenue from cutting rod

Time: O(n²)

Space: O(n)

🎯 Decision Rule (Formulaic):

For rod of length j: CHOOSE: i* = argmax{p[i] + r[j-i] : i = 1 to j} (cut position that maximizes revenue) r[j] = p[i*] + r[j-i*]

Why this rule? Try all possible first cuts, choose best. Remaining piece solved optimally by subproblem.

Recurrence Relation:

r[n] = max{p[i] + r[n-i]} for i = 1 to n Base case: r[0] = 0

Variables:

Variable	Meaning
r[i]	Maximum revenue for rod of length i
p[i]	Price for rod of length i (no cuts)

Matrix Chain Multiplication

Minimize scalar multiplications

Time: O(n³)

Space: O(n²)

🎯 Decision Rule (Formulaic):

For multiplying A[i..j]: CHOOSE: k* = argmin{m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j] : k = i to j-1} (split position minimizing total cost) m[i,j] = m[i,k*] + m[k*+1,j] + p[i-1]·p[k*]·p[j]

Why this rule? Try all possible split points, choose minimum cost. Parenthesization matters!

Recurrence Relation:

m[i,j] = min{m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]} for k = i to j-1 Base case: m[i,i] = 0 (single matrix)

Variables:

Variable	Meaning
m[i,j]	Min scalar multiplications for A[i..j]
p[i]	Dimensions: A[i] is p[i-1] × p[i]
s[i,j]	Optimal split index k for A[i..j]

Longest Common Subsequence (LCS)

Find longest subsequence common to two sequences

Time: O(mn)

Space: O(mn)

🎯 Decision Rule (Formulaic):

IF X[i] = Y[j]: CHOOSE: Include X[i] in LCS LCS[i,j] = LCS[i-1,j-1] + 1 ELSE: CHOOSE: max(LCS[i-1,j], LCS[i,j-1]) (best of excluding X[i] or Y[j])

Why this rule? If characters match, must include. If not, one must be excluded - try both, take best.

Recurrence Relation:

LCS[i,j] = { 0 if i=0 or j=0 LCS[i-1,j-1] + 1 if X[i] = Y[j] max(LCS[i-1,j], LCS[i,j-1]) if X[i] ≠ Y[j] }

Variables:

Variable	Meaning
LCS[i,j]	Length of LCS of X[1..i] and Y[1..j]
m	Length of sequence X
n	Length of sequence Y

TASK: Network Flow Problems

Maximizing flow through a network with capacity constraints

Ford-Fulkerson Method

Iteratively find augmenting paths

Time: O(E·|f*|)

Space: O(V+E)

🎯 Decision Rule (Formulaic):

WHILE exists path p from s to t in residual graph G_f: CHOOSE: Any augmenting path p COMPUTE: c_f(p) = min{c_f(u,v) : (u,v) on p} (bottleneck capacity) FOR EACH edge (u,v) on p: IF forward edge: f(u,v) += c_f(p) IF backward edge: f(v,u) -= c_f(p)

Why this rule? Augmenting path always improves flow. Stop when no path exists → max flow reached.

Residual Capacity Formula:

c_f(u,v) = { c(u,v) - f(u,v) if (u,v) ∈ E (forward) f(v,u) if (v,u) ∈ E (backward) 0 otherwise }

Max-Flow Min-Cut Theorem:

Maximum flow value = Minimum cut capacity

Edmonds-Karp Algorithm

Ford-Fulkerson with BFS for paths

Time: O(VE²)

Space: O(V+E)

🎯 Decision Rule (Formulaic):

CHOOSE: Shortest augmenting path p in residual graph (shortest = fewest edges, use BFS) [Then same augmentation as Ford-Fulkerson]

Why this rule? BFS guarantees shortest path → ensures polynomial time O(VE²), not pseudo-polynomial

Maximum Bipartite Matching

Reduce to max flow problem

Time: O(VE²)

Space: O(V+E)

🎯 Reduction to Max Flow:

Given bipartite graph G = (L ∪ R, E): 1. Add source s with edges to all v ∈ L (capacity 1) 2. Add sink t with edges from all v ∈ R (capacity 1) 3. Direct all edges from L to R (capacity 1) 4. Run max flow algorithm Maximum matching = Maximum flow value

TASK: Divide and Conquer

Breaking problems into subproblems, solving recursively, and combining results

Master Theorem

For analyzing divide-and-conquer recurrences

General Form:

T(n) = aT(n/b) + f(n) where: - a ≥ 1 (number of subproblems) - b > 1 (subproblem size reduction factor) - f(n) = cost of divide + combine

🎯 Decision Rule - Which Case?

COMPARE: f(n) with n^(log_b a) CASE 1: f(n) = O(n^(log_b a - ε)) for ε > 0 [f grows polynomially SLOWER] → T(n) = Θ(n^(log_b a)) CASE 2: f(n) = Θ(n^(log_b a) · log^k n), k ≥ 0 [f grows at SAME rate] → T(n) = Θ(n^(log_b a) · log^(k+1) n) CASE 3: f(n) = Ω(n^(log_b a + ε)) for ε > 0 AND af(n/b) ≤ cf(n) for c < 1 [f grows polynomially FASTER] → T(n) = Θ(f(n))

Common Examples:

Recurrence	a	b	n^(log_b a)	Case	Solution
T(n) = 2T(n/2) + n	2	2	n	2 (k=0)	Θ(n log n)
T(n) = 4T(n/2) + n	4	2	n²	1	Θ(n²)
T(n) = T(n/2) + 1	1	2	1	2 (k=0)	Θ(log n)
T(n) = 7T(n/2) + n²	7	2	n^2.81	1	Θ(n^2.81)

Strassen's Matrix Multiplication

Faster matrix multiplication using divide-and-conquer

Time: O(n^2.81)

Space: O(n²)

Divide, Conquer, Combine:

DIVIDE: Partition n×n matrices into (n/2)×(n/2) blocks A = [A11 A12] B = [B11 B12] [A21 A22] [B21 B22] CONQUER: Compute 7 products (not 8!): P1 = A11(B12 - B22) P2 = (A11 + A12)B22 P3 = (A21 + A22)B11 P4 = A22(B21 - B11) P5 = (A11 + A22)(B11 + B22) P6 = (A12 - A22)(B21 + B22) P7 = (A11 - A21)(B11 + B12) COMBINE: Compute result blocks C11 = P5 + P4 - P2 + P6 C12 = P1 + P2 C21 = P3 + P4 C22 = P5 + P1 - P3 - P7

Recurrence Analysis:

T(n) = 7T(n/2) + Θ(n²) Master Theorem Case 1: n^(log_2 7) ≈ n^2.81 > n² Therefore: T(n) = Θ(n^2.81) [Better than naive Θ(n³)]

Quick Reference: All Complexities by Task

Task	Algorithm	Time	Space	Key Decision Rule
Shortest Path	BFS	O(V+E)	O(V)	FIFO queue → level-by-level
Shortest Path	Dijkstra's	O((V+E) log V)	O(V)	Min distance vertex + relax
Traversal/Ordering	DFS	O(V+E)	O(V)	LIFO stack → depth-first
	Topological Sort	O(V+E)	O(V)	DFS finish times (reverse)
	SCC (Kosaraju)	O(V+E)	O(V)	2 DFS: G then G^T
MST	Kruskal's	O(E log E)	O(V)	Min edge without cycle
MST	Prim's	O((V+E) log V)	O(V)	Min edge to new vertex
Greedy Opt	Activity Selection	O(n log n)	O(1)	Earliest finish time
Greedy Opt	Huffman	O(n log n)	O(n)	Merge two min frequencies
DP Opt	Rod Cutting	O(n²)	O(n)	max over all first cuts
	Matrix Chain	O(n³)	O(n²)	min over all split points
	LCS	O(mn)	O(mn)	Match? +1 : max of exclude
Flow	Ford-Fulkerson	O(E·\|f*\|)	O(V+E)	Any augmenting path
Flow	Edmonds-Karp	O(VE²)	O(V+E)	Shortest augmenting path (BFS)
Divide & Conquer	Master Theorem	-	-	Compare f(n) vs n^(log_b a)
Divide & Conquer	Strassen's	O(n^2.81)	O(n²)	7 subproblems instead of 8