ALGORITHM COMPARISON

& ANALYSIS
A Comprehensive Technical Reference
MST · Shortest Path · String Matching · Greedy Algorithms

TOPIC ALGORITHMS COVERED

Minimum Spanning Tree Prim's | Kruskal's

Shortest Path Dijkstra | Bellman-Ford | Floyd-Warshall

String Pattern Matching Rabin-Karp | Finite Automata | KMP

Greedy Algorithms Fractional Knapsack

Suitable for University Exams · Technical Interviews · Deep Conceptual Study

Covers Pseudocode · Complexity Analysis · Solved Examples · Comparison Tables
Algorithm Comparison & Analysis CS Technical Reference Guide

TABLE OF CONTENTS

1. MINIMUM SPANNING TREE ALGORITHMS ......................... 3

1.1 Prim's Algorithm .................................. 3
1.2 Kruskal's Algorithm ............................... 6
1.3 MST Comparison Table .............................. 9
2. SHORTEST PATH ALGORITHMS ................................ 10
2.1 Dijkstra's Algorithm ............................. 10
2.2 Bellman-Ford Algorithm ........................... 13
2.3 Floyd-Warshall Algorithm ......................... 16
2.4 Shortest Path Comparison Table ................... 19
3. STRING PATTERN MATCHING ALGORITHMS ...................... 20
3.1 Rabin-Karp Algorithm ............................. 20
3.2 Finite Automata String Matching .................. 23
3.3 KMP Algorithm .................................... 25
3.4 String Matching Comparison Table ................. 28
4. FRACTIONAL KNAPSACK ALGORITHM ........................... 29
5. MASTER QUICK REFERENCE .................................. 32

University Exam & Interview Preparation Page 2 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

SECTION 1: MINIMUM SPANNING TREE (MST) ALGORITHMS

A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a spanning tree whose total
edge weight is minimized. A spanning tree includes all V vertices and exactly V-1 edges with no cycles. MST
problems arise frequently in network design, cluster analysis, and approximation algorithms.

■ Key Insight: Every connected weighted graph has at least one MST. If all edge weights are
distinct, the MST is unique.

1.1 PRIM'S ALGORITHM

■ Concept & Intuition

Prim's algorithm builds the MST by starting from an arbitrary source vertex and greedily expanding the tree
one vertex at a time. At every step, it picks the minimum-weight edge that connects a vertex already in the tree
to a vertex outside it. Think of it as growing a single connected component from a seed.

• Belongs to the vertex-based / node-based greedy paradigm.

• Maintains a set of vertices already included in the MST.
• Uses a priority queue (min-heap) to efficiently retrieve the cheapest crossing edge.
• Similar in spirit to Dijkstra's algorithm but minimizes edge weight, not total path cost.

■ Step-by-Step Explanation
■ Step 1: Initialize — pick any starting vertex. Set its key (cost) to 0, all others to ∞.
■ Step 2: Insert all vertices into a min-priority queue keyed by their distance to the MST.
■ Step 3: Extract the vertex u with the minimum key from the queue.
■ Step 4: For each neighbour v of u: if v is still in the queue and weight(u,v) < key[v], update key[v] =
weight(u,v) and parent[v] = u.
■ Step 5: Repeat Steps 3–4 until the queue is empty.
■ Step 6: The MST edges are {(parent[v], v)} for all v ≠ source.

■ Pseudocode
PRIM-MST(G, w, r): // G=graph, w=weight fn, r=root
for each u ∈ G.V: // Initialise
key[u] = ∞ // min edge weight to reach u
parent[u] = NIL
inMST[u] = false
key[r] = 0 // source vertex cost = 0
Q = MIN-PRIORITY-QUEUE(G.V) // enqueue all vertices
while Q is not empty:
u = EXTRACT-MIN(Q) // vertex with smallest key
inMST[u] = true
for each v ∈ Adj[u]: // explore neighbours
if inMST[v] == false AND w(u,v) < key[v]:
parent[v] = u
key[v] = w(u,v) // decrease-key in Q
DECREASE-KEY(Q, v, key[v])
return {(parent[v], v) : v ∈ V \ {r}} // MST edge set

University Exam & Interview Preparation Page 3 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

■ Time & Space Complexity

Implementation Extract-Min Decrease-Key Total Time Space

Simple Array O(V) O(1) O(V²) O(V)

Binary Heap O(log V) O(log V) O((V+E) log V) O(V)

Fibonacci Heap O(log V) O(1) amortised O(E + V log V) O(V)

■ Exam Tip: For dense graphs (E ≈ V²), the simple O(V²) array implementation outperforms the heap-based
version. For sparse graphs use binary heap → O(E log V).

■ Data Structures Used

• Min-Priority Queue (Min-Heap) — for efficient extraction of minimum-key vertex.
• key[] array — stores minimum edge weight connecting each vertex to the MST.
• parent[] array — stores the MST tree structure.
• inMST[] boolean array — tracks which vertices are included.

■ Advantages & Disadvantages

Advantages Disadvantages

Efficient on dense graphs (O(V²) array) Harder to implement than Kruskal's

Works well with adjacency matrix rep. Requires connected graph to start

Naturally produces a connected tree Less intuitive than edge-based approach

Easy to adapt for dynamic graphs Fibonacci heap is complex to implement

Only one component grows — simpler tracking Not suitable for disconnected graphs directly

■ When to Use
• Graph is dense (many edges relative to vertices).
• Stored as an adjacency matrix.
• Need the MST rooted at a specific vertex.
• When memory is limited (only one growing component).

■ Real-World Applications
• Network design — laying cables, roads, or pipelines at minimum cost.
• Cluster analysis — grouping data points with minimum intra-cluster distance.
• Circuit design — minimizing wire length on PCBs.
• Image segmentation — graph-cut algorithms.

■ Fully Solved Example

Consider graph G with vertices {A, B, C, D, E} and edges:

• A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-D: 5, C-E: 6, D-E: 7

Start from vertex A.

University Exam & Interview Preparation Page 4 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

Step Extracted key[] parent[] MST Edge Added

Init — A=0, B=∞, C=∞, D=∞, E=∞ All NIL —

1 A (key=0) A=0, B=2, C=3, D=∞, E=∞ B←A, C←A —

2 B (key=2) A=0, B=2, C=1, D=4, E=∞ C←B, D←B (A,B) w=2

3 C (key=1) A=0, B=2, C=1, D=4, E=6 D stays B, E←C (B,C) w=1

4 D (key=4) A=0, B=2, C=1, D=4, E=6 — (B,D) w=4

5 E (key=6) A=0, B=2, C=1, D=4, E=6 — (C,E) w=6

MST Edges: (A,B)=2, (B,C)=1, (B,D)=4, (C,E)=6 → Total MST Weight = 2+1+4+6 = 13

■ Summary: Prim's grows a single tree from a seed vertex by always adding the cheapest crossing edge.
Complexity: O(V²) with array, O(E log V) with binary heap. Best for dense graphs.

University Exam & Interview Preparation Page 5 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

1.2 KRUSKAL'S ALGORITHM

■ Concept & Intuition

Kruskal's algorithm is an edge-based greedy approach. It considers all edges globally, sorted by weight, and
greedily adds the cheapest edge that does not create a cycle. It builds the MST by merging multiple components
(forests) into one tree. The key data structure is a Disjoint Set Union (DSU / Union-Find).

• Sorts all edges in non-decreasing order of weight.

• Adds an edge if its endpoints belong to different components (no cycle).
• Uses Union-Find for near-O(1) cycle detection.
• Belongs to the edge-based greedy paradigm.

■ Step-by-Step Explanation
■ Step 1: Sort all E edges by weight in ascending order.
■ Step 2: Initialize V disjoint sets (each vertex is its own component).
■ Step 3: For each edge (u, v) in sorted order:
■ If FIND(u) ≠ FIND(v) — endpoints in different sets — add edge to MST and UNION(u, v).
■ Else — skip (would create a cycle).
■ Step 4: Stop when MST has V-1 edges.

■ Pseudocode
KRUSKAL-MST(G, w): // G=graph, w=weight function
MST = {} // empty edge set
for each vertex v ∈ G.V: // DSU init
MAKE-SET(v)
edges = SORT(G.E, key=w) // sort edges ascending
for each edge (u, v) ∈ edges:
if FIND(u) ≠ FIND(v): // no cycle?
MST = MST ∪ {(u, v)}
UNION(u, v)
if |MST| == |G.V| - 1:
break // MST complete
return MST

// DSU with Path Compression + Union by Rank

FIND(x): // returns root of x's set
if parent[x] ≠ x:
parent[x] = FIND(parent[x]) // path compression
return parent[x]

UNION(x, y):
rx, ry = FIND(x), FIND(y)
if rank[rx] < rank[ry]: parent[rx] = ry
elif rank[rx] > rank[ry]: parent[ry] = rx
else: parent[ry] = rx; rank[rx]++

■ Time & Space Complexity

University Exam & Interview Preparation Page 6 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

Operation Complexity

Sorting edges O(E log E) ≡ O(E log V)

DSU operations (with path compress + union by rank) O(α(V)) ≈ O(1) amortised per op

Overall Time Complexity O(E log E)

Space Complexity O(V + E)

■ Advantages & Disadvantages

Advantages Disadvantages

Simple and intuitive to implement Sorting step is always required

Efficient on sparse graphs Slower than Prim's on dense graphs

Works on disconnected graphs (gives a forest) All edges must be known upfront

Easy to parallelize (sort + DSU) DSU with path compression is tricky to code

■ When to Use
• Graph is sparse (E ■ V²).
• Stored as an edge list.
• Graph may be disconnected (produces minimum spanning forest).
• Simpler implementation is preferred.

■ Fully Solved Example

Same graph: vertices {A,B,C,D,E}, edges sorted by weight:

Step Edge Weight FIND(u) FIND(v) Action

1 B-C 1 B C ADD — merge {B} and {C}

2 A-B 2 A B(→BC) ADD — merge {A} and {B,C}

3 A-C 3 A(→ABC) A(→ABC) SKIP — same component

4 B-D 4 A(→ABCD) D ADD — merge {A,B,C} and {D}

5 C-D 5 A(→ABCD) A(→ABCD) SKIP — same component

6 C-E 6 A(→ABCD) E ADD — merge all. MST COMPLETE

MST Edges: B-C=1, A-B=2, B-D=4, C-E=6 → Total = 13 (same result as Prim's ✓)

■ Summary: Kruskal's sorts all edges and greedily adds cheapest non-cycle-forming edges using DSU.
Complexity: O(E log E). Best for sparse graphs or when edge list is given.

University Exam & Interview Preparation Page 7 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

1.3 MST ALGORITHMS — COMPREHENSIVE COMPARISON

Factor Prim's Algorithm Kruskal's Algorithm

Paradigm Vertex-based (node-based) Edge-based

Greedy Strategy Cheapest edge connecting MST to non-MST vertex

Globally cheapest non-cycle edge

Data Structure Priority queue + key[] + parent[] Edge list + DSU (Union-Find)

Graph Type Best for dense graphs Best for sparse graphs

Time Complexity O(V²) array; O(E log V) heap O(E log E)

Space Complexity O(V) O(V + E)

Representation Adjacency matrix / list Edge list (natural)

Handles Disconnected? No — needs connected graph Yes — gives minimum spanning forest

Cycle Detection Implicit (only connects outside vertices) Explicit via DSU

Starting Point Requires a source vertex No source needed — global sort

Implementation Ease Moderate (heap operations) Easier (sort + simple DSU)

Dense Graph (E≈V²) O(V²) — efficient O(V² log V) — slower

Sparse Graph (E≈V) O(V log V) — similar O(V log V) — similar

Parallelism Harder to parallelize Edge sort & DSU are parallelisable

Output Tree rooted at source Set of MST edges (any order)

■ Exam Tip: Both algorithms ALWAYS produce the same total MST weight. The difference is in approach and
efficiency. Prim's = O(E log V) with heap; Kruskal's = O(E log E). Since log E ≤ 2 log V, these are equivalent for
sparse graphs.

University Exam & Interview Preparation Page 8 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

SECTION 2: SHORTEST PATH ALGORITHMS

Shortest path algorithms find the minimum-cost path between vertices in a weighted graph. The choice of
algorithm depends on the graph properties: single-source vs all-pairs, negative weights, negative cycles,
and graph density.

2.1 DIJKSTRA'S ALGORITHM

■ Concept & Intuition

Dijkstra's algorithm solves the single-source shortest path (SSSP) problem for graphs with non-negative
edge weights. It operates like a 'wave' expanding outward from the source, always visiting the nearest unvisited
vertex next (greedy). Once a vertex is visited, its shortest distance is finalized — this is guaranteed only when
weights are non-negative.

• Greedy algorithm — always processes the minimum-distance unvisited vertex.

• Does NOT work with negative edge weights.
• Produces a shortest-path tree rooted at the source.
• Conceptually identical to Prim's MST, but key[v] = dist[s] + w(u,v).

■ Step-by-Step Explanation
■ Step 1: Initialise dist[s] = 0 for source s; dist[v] = ∞ for all others.
■ Step 2: Insert all vertices into a min-priority queue keyed by dist[].
■ Step 3: Extract vertex u with minimum dist.
■ Step 4: For each neighbour v of u: if dist[u] + w(u,v) < dist[v] → update dist[v] (relaxation).
■ Step 5: Repeat until queue is empty or destination is reached.

■ Pseudocode
DIJKSTRA(G, w, s): // s = source vertex
for each v ∈ G.V:
dist[v] = ∞
prev[v] = NIL
dist[s] = 0
Q = MIN-PRIORITY-QUEUE(G.V, key=dist) // all vertices
while Q is not empty:
u = EXTRACT-MIN(Q)
for each v ∈ Adj[u]: // RELAX
if dist[u] + w(u,v) < dist[v]:
dist[v] = dist[u] + w(u,v)
prev[v] = u
DECREASE-KEY(Q, v, dist[v])
return dist[], prev[]

// Reconstruct path to vertex t

PATH(prev, t):
path = []
while t ≠ NIL: [Link](t); t = prev[t]
return path

University Exam & Interview Preparation Page 9 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

■ Complexity Analysis
Implementation Time Complexity Space

Array (linear search) O(V²) O(V)

Binary Heap O((V + E) log V) O(V)

Fibonacci Heap (optimal) O(E + V log V) O(V)

■ Limitations
• Cannot handle negative edge weights — correctness breaks.
• Finds single-source shortest paths only (not all-pairs).
• On very dense graphs, O(V²) implementation is needed.

■ Solved Example
Graph: S→A=4, S→B=2, A→C=3, B→A=1, B→C=5, C→D=2. Find shortest paths from S.

Iteration Extracted dist[S] dist[A] dist[B] dist[C] dist[D]

Init — 0 ∞ ∞ ∞ ∞

1 S (0) 0 4 2 ∞ ∞

2 B (2) 0 3 2 7 ∞

3 A (3) 0 3 2 6 ∞

4 C (6) 0 3 2 6 8

5 D (8) 0 3 2 6 8

Shortest paths from S: A=3, B=2, C=6, D=8

■ Summary: Dijkstra's: greedy SSSP, non-negative weights only. O(E+V log V) with Fibonacci heap.
Optimal for routing in road/network maps.

2.2 BELLMAN-FORD ALGORITHM

■ Concept & Intuition

Bellman-Ford solves SSSP for graphs with negative edge weights. It relaxes ALL edges V-1 times (since any
simple shortest path can have at most V-1 edges). After V-1 rounds, a V-th round check detects negative cycles
(if any distance still decreases, a negative cycle exists).

• Dynamic programming flavour — iteratively improves distance estimates.

• Handles negative weights — unlike Dijkstra.
• Detects negative cycles — extra pass reveals them.
• Slower than Dijkstra but more general.

■ Pseudocode
BELLMAN-FORD(G, w, s): // s = source
for each v ∈ G.V: // init

University Exam & Interview Preparation Page 10 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

dist[v] = ∞; prev[v] = NIL

dist[s] = 0
for i = 1 to |G.V| - 1: // V-1 relaxation rounds
for each edge (u, v) ∈ G.E:
if dist[u] + w(u,v) < dist[v]: // relax
dist[v] = dist[u] + w(u,v)
prev[v] = u
// Negative Cycle Detection
for each edge (u, v) ∈ G.E:
if dist[u] + w(u,v) < dist[v]: // still decreasing?
return 'NEGATIVE CYCLE EXISTS'
return dist[], prev[]

■ Complexity & Limitations

Property Detail

Time Complexity O(V · E)

Space Complexity O(V)

Negative Weights Handles correctly

Negative Cycles Detects and reports

Graph Type Directed or undirected weighted graphs

Limitation Much slower than Dijkstra for non-negative graphs

■ Solved Example
Graph (directed): S→A=6, S→B=7, A→B=8, A→C=-4, B→C=5, B→D=-3, C→S=2, D→C=7, D→A=-2. Source =
S. Run Bellman-Ford with 4 vertices {S,A,B,C,D... actually use 5}.

Simplified 4-node example: Nodes {S, A, B, C}. Edges: S→A=4, S→B=5, A→C=-3, B→C=1. Find shortest
paths from S.

Round Edge Processed dist[S] dist[A] dist[B] dist[C]

Init — 0 ∞ ∞ ∞

1 S→A=4 0 4 ∞ ∞

1 S→B=5 0 4 5 ∞

1 A→C=-3 0 4 5 1

1 B→C=1 0 4 5 1 (no change)

2 All edges 0 4 5 1 (stable)

3 (V-1) All edges 0 4 5 1 (stable)

Neg. check No decrease No negative cycle detected

Result: dist[S]=0, dist[A]=4, dist[B]=5, dist[C]=1

University Exam & Interview Preparation Page 11 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

■ Summary: Bellman-Ford: handles negative weights, detects negative cycles. O(VE). Use when Dijkstra
fails (negative edges). Slower but robust.

University Exam & Interview Preparation Page 12 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

2.3 FLOYD-WARSHALL ALGORITHM

■ Concept & Intuition

Floyd-Warshall is an all-pairs shortest path (APSP) algorithm using dynamic programming. It computes
shortest paths between ALL pairs (i, j) simultaneously. The core idea: dist[i][j] = min(dist[i][j], dist[i][k] +
dist[k][j]) for each intermediate vertex k. We progressively allow more vertices as intermediates.

• DP recurrence: for each k ∈ {1..V}, update all pairs using k as a relay.

• Handles negative weights (but not negative cycles).
• Can detect negative cycles: if dist[i][i] < 0 after the algorithm, a negative cycle exists.
• Simple O(V³) triple-loop — elegant and easy to implement.

■ Pseudocode
FLOYD-WARSHALL(W): // W = weight matrix (V×V)
n = |W| // number of vertices
dist = copy of W // dist[i][j] = direct edge weight
// dist[i][i] = 0; dist[i][j] = ∞ if no direct edge
next = matrix (for path reconstruction), next[i][j] = j if edge exists

for k = 1 to n: // try each vertex as intermediate

for i = 1 to n:
for j = 1 to n:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k] // update path

// Negative Cycle Detection

for i = 1 to n:
if dist[i][i] < 0: return 'NEG CYCLE'
return dist[][], next[][]

// Path Reconstruction
PATH(next, u, v):
if next[u][v] == NIL: return []
path = [u]
while u ≠ v: u = next[u][v]; [Link](u)
return path

■ Complexity
Property Value

Time Complexity O(V³)

Space Complexity O(V²)

Negative Weights Handled correctly

Negative Cycle Detection Yes — dist[i][i] < 0

All-Pairs Output Yes — full V×V distance matrix

University Exam & Interview Preparation Page 13 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

■ Solved Example
Graph (4 nodes): 1→2=3, 1→3=∞, 1→4=7, 2→1=8, 2→3=2, 3→4=1, 4→3=6.

Initial Distance Matrix (dist■):

1 2 3 4

1 0 3 ∞ 7

2 8 0 2 ∞

3 ∞ ∞ 0 1

4 ∞ ∞ 6 0

After k=1 (via vertex 1): dist[2][4] = min(∞, dist[2][1]+dist[1][4]) = min(∞,8+7)=15

After k=2 (via vertex 2): dist[1][3] = min(∞, dist[1][2]+dist[2][3]) = min(∞,3+2)=5

After k=3 (via vertex 3): dist[1][4]=min(7,dist[1][3]+dist[3][4])=min(7,5+1)=6; dist[2][4]=min(15,2+1)=3

After k=4: dist[1][3]=min(5,6+6)=5; dist[2][3]=min(2,3+6)=2 (no changes)

Final Matrix:

1 2 3 4

1 0 3 5 6

2 8 0 2 3

3 ∞ ∞ 0 1

4 ∞ ∞ 6 0

■ Summary: Floyd-Warshall: All-pairs shortest path in O(V³). Handles negative edges. Detects negative
cycles via diagonal. Use when you need all pairwise distances.

University Exam & Interview Preparation Page 14 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

2.4 SHORTEST PATH ALGORITHMS — COMPREHENSIVE COMPARISON

Factor Dijkstra's Bellman-Ford Floyd-Warshall

Problem Type Single-source Single-source All-pairs

Approach Greedy (priority queue) Dynamic Programming (V-1 rounds)

DP (triple loop)

Time Complexity O(E + V log V) O(V · E) O(V³)

Space Complexity O(V) O(V) O(V²)

Negative Weights ■ Not supported ■ Yes ■ Yes

Negative Cycle Detection ■ No ■ Yes (extra pass) ■ Yes (diagonal check)

Dense Graphs O(V²) array — efficient O(V³) — slow O(V³) — natural fit

Sparse Graphs O(E log V) — very fast O(VE) — moderate O(V³) — overkill

Graph Type Directed / Undirected Directed (neg. edges) Directed / Undirected

Output Dist from source + tree Dist from source Full distance matrix

Path Reconstruction Via prev[] array Via prev[] array Via next[][] matrix

Typical Use Cases GPS navigation, routing Financial arbitrage, OSPF Network analysis, all-pairs routing

Implementation Ease Moderate Simple Very simple (3 loops)

■ Exam Tip: Key rules: (1) Negative weights → use Bellman-Ford or Floyd-Warshall. (2) All-pairs → use
Floyd-Warshall if V is small. (3) Non-negative + single source → Dijkstra. (4) Negative cycle detection →
Bellman-Ford (extra pass) or Floyd-Warshall (diagonal).

University Exam & Interview Preparation Page 15 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

SECTION 3: STRING PATTERN MATCHING ALGORITHMS

String pattern matching finds all occurrences of a pattern P of length m within a text T of length n. Naive search
takes O(nm) in the worst case. The algorithms below use clever preprocessing to achieve near-linear
performance.

3.1 RABIN-KARP ALGORITHM

■ Working Principle
Rabin-Karp uses rolling hashing. It computes a hash of the pattern P, then slides a window of length m across
T, computing the hash of each substring in O(1) using a rolling update. When hashes match, it verifies
character-by-character (to handle hash collisions).

• Key idea: Hash comparison is O(1) vs O(m) character comparison.

• Uses polynomial rolling hash: h(s) = (s[0]·d^(m-1) + s[1]·d^(m-2) + … + s[m-1]) mod q
• Rolling update: h_new = (d·(h_old - T[i]·d^(m-1)) + T[i+m]) mod q
• Collision: hashes match but characters differ → spurious hit (re-verify).
• Choosing q large and prime minimizes collision probability.

■ Pseudocode
RABIN-KARP(T, P, d, q): // T=text, P=pattern, d=base, q=prime mod
n = len(T); m = len(P)
h = d^(m-1) mod q // precompute d^(m-1) for rolling
p_hash = 0; t_hash = 0 // pattern & text window hashes
for i = 0 to m-1: // compute initial hashes
p_hash = (d * p_hash + P[i]) mod q
t_hash = (d * t_hash + T[i]) mod q
for i = 0 to n-m: // slide window
if p_hash == t_hash:
if T[i..i+m-1] == P: // verify (avoid spurious hits)
print('Match at', i)
if i < n-m: // rolling hash update
t_hash = (d*(t_hash - T[i]*h) + T[i+m]) mod q
if t_hash < 0: t_hash += q

■ Complexity Analysis
Case Time Note

Best / Average O(n + m) Few or no spurious hits

Worst Case O(nm) All windows cause spurious hits (e.g., q=1)

Space Complexity O(1) Only hash values stored

Preprocessing O(m) Initial hash computation

■ Advantages & Limitations

• Advantage: Naturally extends to 2D pattern matching.

University Exam & Interview Preparation Page 16 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

• Advantage: Excellent average-case performance.

• Advantage: Efficient for multiple pattern search (hash all patterns).
• Limitation: Worst case O(nm) due to collisions.
• Limitation: Correct choice of d and q is critical.

■ Solved Example
Text T = "ABCABDABC", Pattern P = "ABC", d=31, q=101

p_hash = (65·31² + 66·31 + 67) mod 101 = (65·961 + 1986 + 67) mod 101 = (62465 + 2053) mod 101 = 64518
mod 101 = 38

i Window T[i..i+2] t_hash p_hash Hash Match? Char Match? Result

0 ABC 38 38 YES YES ■ Match at 0

1 BCA ?≠38 38 NO — Skip

2 CAB ?≠38 38 NO — Skip

3 ABD ?≠38 38 NO — Skip

4 BDA ?≠38 38 NO — Skip

5 DAB ?≠38 38 NO — Skip

6 ABC 38 38 YES YES ■ Match at 6

■ Summary: Rabin-Karp: rolling hash reduces substring comparison to O(1) on average. Expected
O(n+m), worst O(nm). Great for multi-pattern search.

3.2 FINITE AUTOMATA STRING MATCHING

■ Working Principle
The Finite Automaton (FA) approach builds a Deterministic Finite Automaton (DFA) from the pattern P. Each
state represents how many characters of P have been matched so far. The automaton reads T character by
character; state m (accepting state) signals a match.

• States: {0, 1, 2, …, m} where state k = matched k prefix chars of P.

• Transition function δ(q, a) = length of longest suffix of P[0..q]·a that is a prefix of P.
• Once built, the DFA processes T in O(n) — constant time per character.
• Preprocessing cost O(m · |Σ|) to build the transition table.
• No backtracking during search — each char processed exactly once.

■ Pseudocode
// Phase 1: Preprocess — build transition table δ
COMPUTE-DELTA(P, Sigma): // Sigma = alphabet
m = len(P)
for q = 0 to m:
for each a ∈ Sigma:
k = min(m, q+1)
while k > 0 and P[0..k-1] != (P[0..q-1]+a)[end-k+1..end]:
k = k - 1 // find longest matching prefix

University Exam & Interview Preparation Page 17 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

delta[q][a] = k
return delta

// Phase 2: Search
FA-MATCHER(T, delta, m): // m = pattern length
n = len(T); q = 0 // q = current state
for i = 0 to n-1:
q = delta[q][T[i]] // transition
if q == m: // accepting state
print('Match ending at', i)

■ Complexity Analysis
Phase Time Space

Preprocessing (build δ) O(m² · |Σ|) or O(m · |Σ|) with KMP suffix O(m · |Σ|)

Matching O(n) O(1) (beyond table)

Overall O(m · |Σ| + n) O(m · |Σ|)

■ Solved Example
Pattern P = "ABAB" (m=4), Alphabet Σ = {A, B}

Transition Table δ(q, a):

State q \ Input a A B Meaning

0 (start) 1 0 No prefix matched

1 1 2 Matched "A"

2 3 0 Matched "AB"

3 1 4 Matched "ABA"

4 (accept) 3 0 Matched "ABAB" — MATCH!

Search on T = "ABABCABAB": States: 0→1→2→3→4■→3→0→1→2→3→4■

Matches found at positions: i=3 (0-indexed end), i=8

■ Summary: FA Matching: O(n) search after O(m·|Σ|) preprocessing. No backtracking. Table size can be
large for big alphabets (e.g., Unicode).

University Exam & Interview Preparation Page 18 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

3.3 KNUTH-MORRIS-PRATT (KMP) ALGORITHM

■ Working Principle
KMP avoids redundant comparisons by precomputing a failure function (π) (also called the prefix function or
partial match table). π[i] = length of the longest proper prefix of P[0..i] that is also a suffix. On mismatch at
position j in P, instead of restarting, we shift to π[j-1] — reusing previously matched characters.

• Key insight: Never re-examine text characters already matched.

• π[i] tells us how far to "fall back" in P on a mismatch.
• Text pointer i NEVER moves backward — guaranteed O(n) search.
• Space-efficient: O(m) for the π table, O(1) extra during search.

■ Pseudocode
// Phase 1: Compute Failure Function π
COMPUTE-PI(P):
m = len(P)
pi = array of size m, pi[0] = 0
k = 0 // length of current prefix
for q = 1 to m-1:
while k > 0 and P[k] != P[q]:
k = pi[k-1] // fall back
if P[k] == P[q]: k++
pi[q] = k
return pi

// Phase 2: KMP Search

KMP-MATCHER(T, P):
n = len(T); m = len(P)
pi = COMPUTE-PI(P)
q = 0 // chars matched so far
for i = 0 to n-1:
while q > 0 and P[q] != T[i]: // mismatch
q = pi[q-1] // use failure function
if P[q] == T[i]: q++ // char matched
if q == m: // full match
print('Match at', i - m + 1)
q = pi[q-1] // look for next match

■ Complexity Analysis
Phase Time Space

Failure function π computation O(m) O(m)

Matching phase O(n) O(1) (beyond π)

Overall O(n + m) O(m)

Best/Avg/Worst All O(n + m) Guaranteed linear — no worst case degradation

■ Solved Example

University Exam & Interview Preparation Page 19 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

Pattern P = "ABABCABAB" (m=9)

Step 1: Compute π table:

Index i 0 1 2 3 4 5 6 7 8

P[i] A B A B C A B A B

π[i] 0 0 1 2 0 1 2 3 4

Explanation: π[2]=1 ("A" is both prefix and suffix of "ABA"); π[3]=2 ("AB" is both prefix/suffix of "ABAB"); π[8]=4
("ABAB" is both prefix/suffix of "ABABCABAB").

Step 2: Search T = "AABABCABABCABAB"

i (text) T[i] q (matched) Action Note

0 A 1 Match q=1

1 A 1 Mismatch B≠A, q=π[0]=0, retry Fallback

1 A 1 Match retry at same i

2 B 2 Match q=2

3 A 3 Match q=3

4 B 4 Match q=4

5 C 5 Match q=5

6 A 6 Match q=6

7 B 7 Match q=7

8 A 8 Match q=8

9 B 9→MATCH Pattern found! q=π[8]=4 ■ Match at pos 5

■ Summary: KMP: O(n+m) guaranteed via prefix/failure function. No backtracking on text. Best
general-purpose string matching. Widely used in text editors and DNA search.

3.4 STRING MATCHING — COMPREHENSIVE COMPARISON

Factor Naive Rabin-Karp Finite Automata KMP

Technique Brute force Rolling hash DFA transition table Failure/prefix function

Preprocessing Time O(1) O(m) O(m · |Σ|) O(m)

Search Time (Avg) O(nm) O(n + m) O(n) O(n)

Worst Case Time O(nm) O(nm) O(n) O(n + m)

Space Complexity O(1) O(1) O(m · |Σ|) O(m)

Handles Multiple Patterns No (extend needed) Yes (hash all) With multi-DFA No (use Aho-Corasick)

Alphabet Dependency None None (hash) Yes — table size ∝ |Σ| Minimal

Collision Issue — Yes — spurious hits — —

University Exam & Interview Preparation Page 20 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

Factor Naive Rabin-Karp Finite Automata KMP

Text Pointer Backtrack Yes No No No

Implementation Ease Very easy Moderate Moderate Moderate

Practical Performance Poor (worst case) Very good (avg) Excellent Excellent

Best Use Case Tiny texts Multi-pattern, 2D Repeated search on same pattern
General single-pattern matching

■ Exam Tip: KMP and FA both achieve O(n+m) but KMP uses O(m) space vs O(m·|Σ|) for FA. FA is faster in
practice if the alphabet is small. Rabin-Karp shines for multi-pattern search (hash all patterns into a set, O(1)
lookup).

University Exam & Interview Preparation Page 21 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

SECTION 4: FRACTIONAL KNAPSACK ALGORITHM

■ Problem Statement
Given n items, each with a value v[i] and weight w[i], and a knapsack of capacity W, maximize total value.
Unlike the 0/1 Knapsack, here you may take fractions of items (e.g., take 60% of item 3). This crucial
difference makes the greedy approach optimal.

■ Why Greedy Works Here

The greedy choice property holds: always take the item (or fraction) with the highest value-to-weight ratio
(v/w) first. This never leads to a suboptimal solution because:

• Items are infinitely divisible — we can always fill exactly to capacity W.

• Taking the best ratio item first maximizes value per unit of capacity used.
• Exchange argument: Any solution not following ratio-sorted order can be improved by swapping.
• This does NOT apply to 0/1 Knapsack (items indivisible) → requires DP.
■ Key Insight: Greedy works for Fractional Knapsack because the problem has the GREEDY
CHOICE PROPERTY. For 0/1 Knapsack, greedy fails — use Dynamic Programming (O(nW)) instead.

■ Algorithm
■ Step 1: Compute ratio = v[i] / w[i] for each item.
■ Step 2: Sort items in descending order of ratio.
■ Step 3: Greedily fill the knapsack:
■ If current item fits entirely → take all of it (add full v[i]).
■ Else → take the fraction that fills remaining capacity.
■ Step 4: Return total value accumulated.

■ Pseudocode
FRACTIONAL-KNAPSACK(items, W): // items = [(v,w), ...], W = capacity
for each item: ratio[i] = v[i] / w[i] // compute ratios
SORT(items, key=ratio, descending=True) // O(n log n)
total_value = 0.0
remaining_cap = W
for each item (v, w) in sorted order:
if remaining_cap == 0: break // knapsack full
take = min(w, remaining_cap) // take as much as possible
total_value += take * (v / w) // add proportional value
remaining_cap -= take
return total_value

■ Complexity Analysis
Operation Complexity Note

Sorting (dominant step) O(n log n) Sort by v/w ratio

Greedy selection O(n) Single pass through sorted items

University Exam & Interview Preparation Page 22 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

Operation Complexity Note

Overall Time O(n log n) Sorting dominates

Space Complexity O(1) Sorting in place (O(log n) stack for sort)

University Exam & Interview Preparation Page 23 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

■ Detailed Solved Example

Capacity W = 50 kg. Items:

Item Value (■) Weight (kg) Ratio v/w

Item 1 60 10 6.00

Item 2 100 20 5.00

Item 3 120 30 4.00

Item 4 80 40 2.00

Item 5 50 25 2.00

Step 1: Sort by ratio descending:

Rank Item Value Weight Ratio Cumulative Weight Action

1st Item 1 60 10 6.00 10 kg (10/50) Take ALL (fits)

2nd Item 2 100 20 5.00 30 kg (30/50) Take ALL (fits)

3rd Item 3 120 30 4.00 30+30=60 → over! Take 20/30 = 2/3 fraction

4th Item 4 80 40 2.00 — Knapsack FULL — stop

Step 2: Calculate total value:

Item Amount Taken Value Contribution Calculation

Item 1 10 kg (100%) ■60.00 10 × (60/10) = 10 × 6 = 60

Item 2 20 kg (100%) ■100.00 20 × (100/20) = 20 × 5 = 100

Item 3 20 kg (66.67%) ■80.00 20 × (120/30) = 20 × 4 = 80

TOTAL 50 kg (full!) ■240.00 Maximum achievable value

Answer: Maximum value = ■240.00 for 50 kg capacity.

■ Note: If this were a 0/1 Knapsack (no fractions), the greedy solution would fail. For example, taking Item 3
(■120, 30kg) + Item 2 (■100, 20kg) = ■220 is suboptimal vs the DP solution. Always check: is the problem
fractional or 0/1?

■ Summary: Fractional Knapsack: sort by value/weight ratio, greedily fill. O(n log n). Greedy is OPTIMAL
here because items are divisible. 0/1 Knapsack requires O(nW) DP — greedy does NOT work there.

University Exam & Interview Preparation Page 24 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

SECTION 5: MASTER QUICK REFERENCE

5.1 COMPLEXITY CHEAT SHEET

Algorithm Time (Best) Time (Avg) Time (Worst) Space Category

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

Prim's (array) O(V²) O(V²) O(V²) O(V) MST

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

Dijkstra (heap) O(E+V log V) O(E+V log V) O(E+V log V) O(V) SSSP

Bellman-Ford O(E) O(VE) O(VE) O(V) SSSP

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

Rabin-Karp O(n+m) O(n+m) O(nm) O(1) String Match

Finite Automata O(n) O(n) O(n) O(m·|Σ|) String Match

KMP O(n+m) O(n+m) O(n+m) O(m) String Match

Fractional Knapsack O(n log n) O(n log n) O(n log n) O(1) Greedy

5.2 DECISION GUIDE — WHICH ALGORITHM TO USE?

Situation / Constraint Recommended Algorithm Reason

Find MST, dense graph, adj. matrix Prim's (array — O(V²)) Avoids priority queue overhead

Find MST, sparse graph, edge list Kruskal's Sorting + DSU is optimal for sparse E

SSSP, non-negative weights Dijkstra's Fastest SSSP for non-neg weights

SSSP, negative edge weights Bellman-Ford Only SSSP that handles negative weights

Detect negative cycles Bellman-Ford or Floyd-Warshall Built-in detection mechanism

All-pairs shortest paths Floyd-Warshall Natural O(V³) DP for all pairs

All-pairs, sparse, large V Johnson's (Dijkstra + Bellman-Ford) O(VE + V² log V)

Single pattern in text (general) KMP O(n+m) guaranteed, O(m) space

Single pattern, small alphabet Finite Automata O(n) search after preprocessing

Multiple patterns in text Rabin-Karp or Aho-Corasick Hash set lookup or multi-pattern DFA

2D pattern matching Rabin-Karp (2D hash) Natural extension of rolling hash

Maximize value (divisible items) Fractional Knapsack (Greedy) Greedy is optimal for fractional

Maximize value (0/1 items) Dynamic Programming Greedy fails — DP is needed

5.3 KEY THEOREMS & PROPERTIES

University Exam & Interview Preparation Page 25 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

• MST Cut Property: For any cut of G, the minimum-weight crossing edge belongs to some MST.
• MST Cycle Property: For any cycle in G, the maximum-weight edge does NOT belong to any MST (if
unique).
• Dijkstra Correctness: When a vertex is extracted from the min-heap, its dist[] is finalized (holds only for
non-negative weights).
• Bellman-Ford Correctness: After V-1 relaxations, all shortest paths (without negative cycles) are correctly
computed.
• Floyd-Warshall Optimality: The optimal substructure — a shortest path's subpath is also a shortest path —
justifies the DP recurrence.
• KMP Linear Time: The text pointer i never decreases (only j falls back via π), guaranteeing O(n) for the
search phase.
• Greedy Knapsack Optimality: Proven by exchange argument — swapping any other choice for the
highest-ratio item cannot increase total value.

5.4 COMMON EXAM PITFALLS

• ■ Using Dijkstra with negative edges — distances become incorrect. Use Bellman-Ford.
• ■ Using greedy for 0/1 Knapsack — greedy fails; always use DP.
• ■ Confusing MST weight with shortest path — they are fundamentally different objectives.
• ■ Assuming Prim's and Kruskal's give the same edge set — they give the same WEIGHT but possibly
different edge sets (when weights are non-unique).
• ■ Ignoring collision handling in Rabin-Karp — always verify character-by-character on hash match.
• ■ Floyd-Warshall on negative cycles — the algorithm produces incorrect results; detect first via diagonal.
• ■ Confusing π[i] in KMP — it is the longest PROPER prefix that is also a suffix (not counting the full string
itself).
• ■ Forgetting to check for negative cycles — Bellman-Ford extra pass; Floyd-Warshall diagonal check.

University Exam & Interview Preparation Page 26 © 2025 CS Algorithm Reference

Algorithm Comparison & Analysis CS Technical Reference Guide

5.5 ALGORITHM STRATEGY PATTERNS

Understanding the underlying algorithm design paradigm helps you derive algorithms from first principles in
exams and interviews:

Paradigm Core Idea Examples in This Guide

Greedy Make locally optimal choice; never reconsiderPrim's, Kruskal's, Dijkstra's, Fractional Knapsack

Dynamic Programming Optimal substructure + overlapping subproblems;

Bellman-Ford,
build from Floyd-Warshall
smaller

Divide & Conquer Split, solve subproblems recursively, combineNot covered here (Merge Sort, FFT)

Hashing Map data to integer fingerprint for O(1) lookupRabin-Karp (rolling hash)

Finite Automata Model computation as state transitions FA String Matching

Amortized Analysis Expensive ops are rare; average cost per op is

KMPlow(text pointer never decreases), DSU

5.6 GRAPH REPRESENTATION GUIDE

Representation Space Edge Check Neighbour Iteration Best For

Adjacency Matrix O(V²) O(1) O(V) Dense graphs, Floyd-Warshall

Adjacency List O(V+E) O(degree) O(degree) Sparse graphs, Dijkstra, BFS/DFS

Edge List O(E) O(E) O(E) Kruskal's (sort edges directly)

END OF DOCUMENT — Algorithm Comparison & Analysis Reference Guide

Prepared for University Examination & Technical Interview Preparation

University Exam & Interview Preparation Page 27 © 2025 CS Algorithm Reference