DAA - Unit 3 | ankushraj.dev

🗺️Chapter 1 — Graph Algorithms

🗺️ GRAPH ALGORITHMS — MIND MAP

Representation → Adjacency Matrix O(V²) space | Adjacency List O(V+E) space

DFS → Stack/Recursion | O(V+E) | Explores depth-first | Applications: cycle detection, topo sort

BFS → Queue | O(V+E) | Explores level-by-level | Applications: shortest path (unweighted), level order

Topological Sort → DFS-based or Kahn's (in-degree) | Only for DAGs (Directed Acyclic Graphs)

Dijkstra → Greedy | Single Source Shortest Path | No negative weights | O(V²) or O(E log V)

Bellman-Ford → DP | Single Source | Handles negative weights | Detects negative cycles | O(VE)

Floyd-Warshall → DP | All-Pairs Shortest Path | O(V³) | D[i][j] = min(D[i][j], D[i][k]+D[k][j])

Sollin's (Borůvka's) → MST | Each component picks cheapest outgoing edge | O(E log V)

1. Representation of Graphs

Graph G = (V, E) where V = set of vertices, E = set of edges.
Types: Directed/Undirected, Weighted/Unweighted, Cyclic/Acyclic
Two main representations: Adjacency Matrix & Adjacency List

Adjacency Matrix

Structure: V×V matrix where A[i][j] = 1 (or weight) if edge (i,j) exists, else 0.
Space: O(V²)
Edge lookup: O(1) — direct array access
Best for: Dense graphs (many edges), frequent edge queries

Adjacency List

Structure: Array of V linked lists. Each list contains neighbors of vertex i.
Space: O(V + E) — much better for sparse graphs
Edge lookup: O(degree of vertex)
Best for: Sparse graphs (few edges), traversal algorithms

Feature	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Edge check (u,v)	O(1)	O(degree(u))
Add edge	O(1)	O(1)
List all neighbors	O(V)	O(degree)
Best for	Dense graphs	Sparse graphs

Graph: 1--2, 1--3, 2--4, 3--4 Adjacency Matrix: Adjacency List: 1 2 3 4 1 → [2, 3] 1 [ 0 1 1 0 ] 2 → [1, 4] 2 [ 1 0 0 1 ] 3 → [1, 4] 3 [ 1 0 0 1 ] 4 → [2, 3] 4 [ 0 1 1 0 ]

Graph Representation — Same graph, two representations

2. Depth First Search (DFS) & Breadth First Search (BFS)

DFS: Explores as deep as possible before backtracking. Uses Stack (or recursion). Marks visited vertices to avoid cycles.

BFS: Explores all neighbors at current level before going deeper. Uses Queue. Finds shortest path in unweighted graphs.

DFS Algorithm

DFS Steps:
1. Mark start vertex as visited, push to stack (or call recursively)
2. For each unvisited neighbor of current vertex: recurse
3. Backtrack when no unvisited neighbors remain
4. Repeat for all unvisited vertices (for disconnected graphs)

Time: O(V + E) | Space: O(V) for visited array + recursion stack

BFS Algorithm

BFS Steps:
1. Enqueue start vertex, mark as visited
2. Dequeue front vertex, process it
3. Enqueue all unvisited neighbors, mark them visited
4. Repeat until queue is empty

Time: O(V + E) | Space: O(V) for queue + visited array

Solved Example — DFS and BFS Traversal

Q: For graph with edges: 0-1, 0-2, 1-3, 1-4, 2-5. Starting from vertex 0, find DFS and BFS order.

Graph structure:
0 → [1, 2], 1 → [0, 3, 4], 2 → [0, 5], 3 → [1], 4 → [1], 5 → [2]

DFS from 0: Visit 0 → go deep to 1 → go deep to 3 → backtrack → 4 → backtrack to 0 → 2 → 5
DFS Order: 0, 1, 3, 4, 2, 5

BFS from 0: Queue=[0] → dequeue 0, enqueue [1,2] → dequeue 1, enqueue [3,4] → dequeue 2, enqueue [5] → dequeue 3 → dequeue 4 → dequeue 5
BFS Order: 0, 1, 2, 3, 4, 5

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int V = 6;
vector<int> adj[6];  // Adjacency list

// DFS — recursive
void DFS(int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";
    for (int u : adj[v]) {
        if (!visited[u])
            DFS(u, visited);
    }
}

// BFS — iterative using queue
void BFS(int start) {
    bool visited[6] = {false};
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << " ";
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

int main() {
    // Add edges: 0-1,0-2,1-3,1-4,2-5
    adj[0] = {1,2}; adj[1] = {0,3,4}; adj[2] = {0,5};
    adj[3] = {1}; adj[4] = {1}; adj[5] = {2};
    bool vis[6] = {false};
    cout << "DFS: "; DFS(0, vis);   // Output: 0 1 3 4 2 5
    cout << "\nBFS: "; BFS(0);       // Output: 0 1 2 3 4 5
}

Feature	DFS	BFS
Data Structure	Stack (or Recursion)	Queue
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V) — recursion stack	O(V) — queue
Shortest Path	No guarantee	Yes (unweighted)
Applications	Topological sort, cycle detection, SCCs	Level order, shortest path, bipartite check

3. Topological Sort

Topological Sort: A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u → v), vertex u appears before v in the ordering.

Key Requirement: Graph MUST be a DAG (no cycles). If cycle exists, topological sort is impossible.
Applications: Task scheduling, course prerequisites, build systems, dependency resolution.

💡 Real-Life Analogy:
In a university, some courses have prerequisites: Math → Physics → Engineering. Topological sort gives a valid order to take courses so prerequisites are always done first.

Method 1: DFS-based (Recursive)

Steps:
1. For each unvisited vertex, call DFS
2. After fully exploring all descendants of a vertex, push it onto a stack
3. Pop all elements from stack → gives topological order

Time: O(V + E) | Space: O(V)

Method 2: Kahn's Algorithm (BFS / In-degree based)

Steps:
1. Compute in-degree of all vertices
2. Enqueue all vertices with in-degree = 0
3. Dequeue vertex u, add to result, decrease in-degree of all neighbors
4. If neighbor's in-degree becomes 0, enqueue it
5. If result size < V → cycle exists (no valid topological sort)

Time: O(V + E) | Space: O(V)

Solved Example

Q: Find topological sort for DAG: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1

In-degrees: 0→2, 1→2, 2→1, 3→1, 4→0, 5→0

Kahn's Steps:
Queue = [4, 5] (in-degree 0)
Dequeue 4 → result=[4], reduce in-degree of 0→1, 1→1; Queue=[5]
Dequeue 5 → result=[4,5], reduce 2→0, 0→0; Queue=[2,0]
Dequeue 2 → result=[4,5,2], reduce 3→0; Queue=[0,3]
Dequeue 0 → result=[4,5,2,0]; Queue=[3]
Dequeue 3 → result=[4,5,2,0,3], reduce 1→0; Queue=[1]
Dequeue 1 → result=[4,5,2,0,3,1]

Topological Order: 4 → 5 → 2 → 0 → 3 → 1
(Other valid orders also possible depending on tie-breaking)

💡 Key Points:
• Topological sort is NOT unique — multiple valid orderings exist for most DAGs
• If DFS-based: result is reverse of finish order → reverse the stack
• If Kahn's: result size ≠ V → cycle detected → no topological sort possible

4. Dijkstra's Algorithm — Single Source Shortest Path

Dijkstra's Algorithm: Finds shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights.

Strategy: Greedy — always process the unvisited vertex with minimum distance first.
Data Structure: Priority Queue (min-heap) or simple array
Time: O(V²) with array | O((V+E) log V) with min-heap

Algorithm Steps:
1. Initialize dist[source] = 0, dist[all others] = ∞
2. Mark all vertices as unvisited
3. Pick unvisited vertex u with minimum dist[u] (the greedy choice)
4. For each neighbor v of u: if dist[u] + w(u,v) < dist[v], update dist[v] (relaxation)
5. Mark u as visited (its distance is now finalized)
6. Repeat steps 3–5 until all vertices visited

Solved Numerical

Q: Find shortest path from vertex A using Dijkstra's Algorithm.
Edges: A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2, D-F:6, E-F:3

Initial: dist = {A:0, B:∞, C:∞, D:∞, E:∞, F:∞}, Unvisited = {A,B,C,D,E,F}

Iteration 1: Pick A (dist=0)
Relax B: 0+4=4 < ∞ → dist[B]=4
Relax C: 0+2=2 < ∞ → dist[C]=2
Mark A visited. dist = {A:0, B:4, C:2, D:∞, E:∞, F:∞}

Iteration 2: Pick C (dist=2, minimum unvisited)
Relax B: 2+1=3 < 4 → dist[B]=3
Relax D: 2+8=10 < ∞ → dist[D]=10
Relax E: 2+10=12 < ∞ → dist[E]=12
Mark C visited. dist = {A:0, B:3, C:2, D:10, E:12, F:∞}

Iteration 3: Pick B (dist=3)
A already visited, skip
Relax D: 3+5=8 < 10 → dist[D]=8
Mark B visited. dist = {A:0, B:3, C:2, D:8, E:12, F:∞}

Iteration 4: Pick D (dist=8)
Relax E: 8+2=10 < 12 → dist[E]=10
Relax F: 8+6=14 < ∞ → dist[F]=14
Mark D visited. dist = {A:0, B:3, C:2, D:8, E:10, F:14}

Iteration 5: Pick E (dist=10)
Relax F: 10+3=13 < 14 → dist[F]=13
Mark E visited.

Iteration 6: Pick F (dist=13) → Mark F visited.

Final Shortest Distances from A:
A→A=0, A→B=3, A→C=2, A→D=8, A→E=10, A→F=13

⚠️ Dijkstra's Limitation:
• Cannot handle negative weight edges — gives wrong results
• Cannot detect negative weight cycles
• For negative weights, use Bellman-Ford instead

5. Bellman-Ford Algorithm

Bellman-Ford: Dynamic Programming algorithm for Single Source Shortest Path that handles negative weight edges and can detect negative weight cycles.

Key Idea: Relax ALL edges V-1 times. After V-1 iterations, shortest paths are finalized (for graphs without negative cycles).
Time: O(V × E) | Space: O(V)

Algorithm Steps:
1. dist[source] = 0, dist[all others] = ∞
2. Repeat V-1 times:
For every edge (u, v, w): if dist[u] + w < dist[v], update dist[v]
3. Negative cycle detection: Do one more relaxation (V-th iteration)
If any dist[v] still decreases → negative cycle exists!

Solved Numerical

Q: Find shortest paths from vertex 0 using Bellman-Ford.
Edges: 0→1:4, 0→2:5, 1→3:3, 2→1:-6, 3→4:2

V=5, E=5. Run V-1 = 4 iterations.

Initial: dist = [0, ∞, ∞, ∞, ∞]

Iteration 1 (relax all edges):
Edge 0→1:4 → dist[1] = min(∞, 0+4) = 4
Edge 0→2:5 → dist[2] = min(∞, 0+5) = 5
Edge 1→3:3 → dist[3] = min(∞, 4+3) = 7
Edge 2→1:-6 → dist[1] = min(4, 5-6) = -1
Edge 3→4:2 → dist[4] = min(∞, 7+2) = 9
dist = [0, -1, 5, 7, 9]

Iteration 2:
Edge 1→3:3 → dist[3] = min(7, -1+3) = 2
Edge 3→4:2 → dist[4] = min(9, 2+2) = 4
dist = [0, -1, 5, 2, 4]

Iterations 3 & 4: No further updates.

Final Shortest Distances from 0: [0, -1, 5, 2, 4]
No negative cycle detected (V-th iteration causes no change)

Feature	Dijkstra's	Bellman-Ford
Strategy	Greedy	Dynamic Programming
Time Complexity	O(V²) or O(E log V)	O(V × E) — slower
Negative Weights	Not supported ✗	Supported ✓
Negative Cycle Detection	No	Yes ✓
Scope	Single Source	Single Source

6. Floyd-Warshall Algorithm — All-Pairs Shortest Path

Floyd-Warshall: Dynamic Programming algorithm that finds shortest paths between ALL pairs of vertices. Works with negative weights but not negative cycles.

Core Recurrence:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Meaning: "Can we go from i to j through intermediate vertex k in a shorter path?"
Time: O(V³) | Space: O(V²)

Algorithm Steps:
1. Initialize D[i][j] = weight(i,j) if edge exists, 0 if i=j, ∞ otherwise
2. For k = 1 to V (each vertex as intermediate):
   For i = 1 to V:
     For j = 1 to V:
       D[i][j] = min(D[i][j], D[i][k] + D[k][j])
3. Result: D[i][j] = shortest path from i to j

Solved Numerical

Q: Apply Floyd-Warshall. Weight matrix:
W = [[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]

Initial D (= W):

1 2 3 4 1 [ 0 3 ∞ 7 ] 2 [ 8 0 2 ∞ ] 3 [ 5 ∞ 0 1 ] 4 [ 2 ∞ ∞ 0 ]

k=1 (through vertex 1):
D[2][4] = min(∞, D[2][1]+D[1][4]) = min(∞, 8+7) = 15
D[3][2] = min(∞, D[3][1]+D[1][2]) = min(∞, 5+3) = 8
D[3][4] = min(1, D[3][1]+D[1][4]) = min(1, 5+7) = 1 (no change)
D[4][2] = min(∞, D[4][1]+D[1][2]) = min(∞, 2+3) = 5
D[4][3] = min(∞, D[4][1]+D[1][3]) = min(∞, 2+∞) = ∞

k=2 (through vertex 2):
D[1][3] = min(∞, D[1][2]+D[2][3]) = min(∞, 3+2) = 5
D[1][4] = min(7, D[1][2]+D[2][4]) = min(7, 3+15) = 7 (no change)
D[4][3] = min(∞, D[4][2]+D[2][3]) = min(∞, 5+2) = 7

k=3 (through vertex 3):
D[1][4] = min(7, D[1][3]+D[3][4]) = min(7, 5+1) = 6
D[2][4] = min(15, D[2][3]+D[3][4]) = min(15, 2+1) = 3
D[4][4] = min(0, D[4][3]+D[3][4]) = 0 (diagonal, skip)

k=4 (through vertex 4):
D[1][2] = min(3, D[1][4]+D[4][2]) = min(3, 6+5) = 3 (no change)
D[2][1] = min(8, D[2][4]+D[4][1]) = min(8, 3+2) = 5
D[3][1] = min(5, D[3][4]+D[4][1]) = min(5, 1+2) = 3

Final Distance Matrix D:

1 2 3 4 1 [ 0 3 5 6 ] 2 [ 5 0 2 3 ] 3 [ 3 8 0 1 ] 4 [ 2 5 7 0 ]

7. Sollin's Algorithm (Borůvka's Algorithm) — Minimum Spanning Tree

Sollin's Algorithm (also called Borůvka's Algorithm) finds the Minimum Spanning Tree (MST) of a graph. It is one of the oldest MST algorithms and works by simultaneously adding the cheapest edge from each component.

Time Complexity: O(E log V)
Key Feature: Can be parallelized easily (all components work simultaneously)

Algorithm Steps:
1. Start: Each vertex is its own component (V components)
2. Phase: For each component, find the cheapest edge that connects it to a different component
3. Add all these cheapest edges to the MST (use Union-Find to merge components)
4. Repeat phases until only 1 component remains (MST complete)
5. Number of phases = O(log V) since each phase at least halves the components

Solved Example

Q: Find MST using Sollin's Algorithm.
Graph: A-B:4, A-C:2, B-C:3, B-D:5, C-D:1, D-E:6, C-E:8

Initial Components: {A}, {B}, {C}, {D}, {E} — 5 components

Phase 1: Find cheapest outgoing edge for each component:
• {A}: cheapest edge A-C:2
• {B}: cheapest edge B-C:3
• {C}: cheapest edge C-D:1
• {D}: cheapest edge C-D:1 (D→C)
• {E}: cheapest edge D-E:6
Add unique edges: C-D:1, A-C:2, B-C:3, D-E:6
(C-D appears from both C and D — add once)
MST so far: {C-D:1, A-C:2, B-C:3, D-E:6} = cost 12
Components after merge: {A,B,C,D,E} — all merged in one phase!

MST Edges: C-D(1) + A-C(2) + B-C(3) + D-E(6) = Total weight = 12

Feature	Kruskal's	Prim's	Sollin's (Borůvka's)
Approach	Sort all edges, add min	Grow one tree from source	All components find min edge simultaneously
Time	O(E log E)	O(V²) or O(E log V)	O(E log V)
Data Structure	Union-Find	Min-heap	Union-Find
Parallelizable	No	No	Yes ✓

⚙️Chapter 2 — Computational Complexity

⚙️ COMPUTATIONAL COMPLEXITY — MIND MAP

P (Polynomial) → Solvable in polynomial time O(n^k) | Easy problems | Examples: sorting, shortest path

NP (Non-deterministic Polynomial) → Solution VERIFIABLE in polynomial time | Includes P as subset | P ⊆ NP

NP-Hard → At least as hard as hardest NP problem | Not necessarily in NP | Solved by reducing known NP-Hard to it

NP-Complete → In NP AND NP-Hard | "Hardest problems in NP" | Examples: SAT, TSP, Hamiltonian Cycle, Vertex Cover

Reduction → Prove NP-Hard by reducing known NP-Complete to new problem in polynomial time

P vs NP? → Greatest open problem in CS: Does P = NP? (Most believe P ≠ NP but unproven)

1. Basic Concepts — P, NP, NP-Hard, NP-Complete

Decision Problem vs Optimization Problem:
• Decision Problem: Answer is YES or NO. Example: "Is there a path of length ≤ k?"
• Optimization Problem: Find minimum/maximum. Example: "Find shortest path"
Complexity classes focus on decision problems (easier to classify).

Class P

P (Polynomial Time):
Set of decision problems solvable by a deterministic algorithm in polynomial time O(n^k) for some constant k.

Examples:
• Sorting (O(n log n))
• Shortest path — Dijkstra (O(V²))
• Matrix multiplication (O(n³))
• Binary search (O(log n))
• GCD — Euclid's (O(log n))

Intuition: Problems we can solve efficiently. "Tractable" problems.

Class NP

NP (Nondeterministic Polynomial):
Set of decision problems for which a given solution can be VERIFIED in polynomial time.

Examples:
• Boolean Satisfiability (SAT): Given a truth assignment, check if formula is satisfied — O(n)
• Travelling Salesman: Given a tour, verify if cost ≤ k — O(n)
• Hamiltonian Cycle: Given a cycle, verify it visits all vertices — O(n)
• Graph Coloring: Given a coloring, verify validity — O(E)

Key Insight: Verification is easy (polynomial). Finding the solution might be hard.
Fact: P ⊆ NP (everything in P is also in NP — if we can solve it, we can verify it)

Class NP-Hard

NP-Hard:
Problems at least as hard as the hardest problems in NP. Every NP problem reduces to an NP-Hard problem in polynomial time. NP-Hard problems may not be in NP (might not be decidable/verifiable in polynomial time).

Meaning: If we could solve any NP-Hard problem in polynomial time, we could solve ALL NP problems in polynomial time (P = NP).

Examples: Halting problem (not in NP), TSP optimization version, Integer Linear Programming

Class NP-Complete

NP-Complete (NPC):
Problems that are BOTH in NP AND NP-Hard. These are the hardest problems within NP.

To prove NP-Complete:
1. Show it's in NP (verify solution in polynomial time)
2. Show it's NP-Hard (reduce a known NPC problem to it in polynomial time)

Famous NP-Complete problems:
• SAT (Boolean Satisfiability) — first NPC problem (Cook's theorem, 1971)
• 3-SAT — special case of SAT
• Hamiltonian Cycle — visit all vertices exactly once
• Travelling Salesman Problem (TSP) — decision version
• Vertex Cover — minimum set of vertices covering all edges
• Clique — find k-clique in graph
• Graph Coloring (k ≥ 3) — color with k colors, no adjacent same color

Complexity Classes Relationship: ┌─────────────────────────────────────────┐ │ NP │ │ ┌────────────────────────────────┐ │ │ │ P │ │ │ │ (solvable in poly time) │ │ │ └────────────────────────────────┘ │ │ (verifiable in poly time) │ └──────────────────┬──────────────────────┘ │ ┌─────────────┼─────────────┐ │ NP-Complete │ │ (NP ∩ NP-Hard) │ │ SAT, TSP, Ham Cycle, ... │ └─────────────┬─────────────┘ │ ⊆ ┌─────────────┴─────────────┐ │ NP-Hard │ │ (≥ hardest NP problems) │ └───────────────────────────┘ If P = NP: P = NP = NP-Complete (all merge) Most believe: P ≠ NP (NPC problems truly hard to solve)

Complexity Classes Hierarchy

2. Proof of NP-Hardness and NP-Completeness

Polynomial Reduction (≤p):
Problem A reduces to Problem B (written A ≤p B) if:
• Any instance of A can be transformed to an instance of B in polynomial time
• Solution to B gives solution to A

Meaning: B is at least as hard as A. If B is easy (in P), then A is also easy.

Proof Framework — Proving Problem X is NP-Complete:
Step 1 (NP membership): Show X ∈ NP
→ Given a certificate (potential solution), verify it in polynomial time

Step 2 (NP-Hardness): Show X is NP-Hard
→ Choose a known NP-Complete problem Y (e.g., SAT, 3-SAT, Clique)
→ Show Y ≤p X (reduce Y to X in polynomial time)
→ This proves every NP problem reduces to X

Conclusion: X is in NP AND NP-Hard → X is NP-Complete ✓

Example: Proving Vertex Cover is NP-Complete

Vertex Cover Problem: Given graph G=(V,E) and integer k, does G have a vertex cover of size ≤ k? (A vertex cover is a set S ⊆ V such that every edge has at least one endpoint in S.)

Step 1 — Show Vertex Cover ∈ NP:
Certificate = a set S of k vertices. Verification: check every edge (u,v) has u∈S or v∈S. This takes O(E) time → polynomial. ✓

Step 2 — Show Vertex Cover is NP-Hard (reduce from Clique):
Clique is NP-Complete. We show Clique ≤p Vertex Cover.
Reduction: Given (G, k) for Clique problem, create (G', n-k) for Vertex Cover where G' = complement graph of G.
Key Fact: G has a clique of size k ↔ complement(G) has a vertex cover of size n-k
The complement graph can be computed in O(V²) — polynomial.
∴ Vertex Cover is NP-Hard.

Conclusion: Vertex Cover is NP-Complete ✓

Cook's Theorem (Historical)

Cook's Theorem (1971): SAT (Boolean Satisfiability) is NP-Complete — the first problem proven NP-Complete.

SAT: Given a boolean formula in CNF, is there an assignment of TRUE/FALSE to variables that makes the formula TRUE?

Significance: Once SAT was proven NP-Complete, all other NP-Complete proofs became easier — just reduce SAT (or a known NPC problem) to the new problem!

Karp's 21 problems (1972): Showed 21 famous combinatorial problems are all NP-Complete by chained reductions.

Property	P	NP	NP-Hard	NP-Complete
Solvable in poly time	✓	Unknown	Unknown	Unknown
Verifiable in poly time	✓	✓	Not required	✓
Every NP problem reduces to it	No	No	✓	✓
Examples	Sorting, BFS, GCD	SAT, TSP, Clique	Halting Problem	SAT, Vertex Cover, TSP

🔤Chapter 3 — Miscellaneous Topics

🔤 MISCELLANEOUS TOPICS — MIND MAP

Euclid's GCD → gcd(a,b) = gcd(b, a mod b) | Base: gcd(a,0)=a | O(log min(a,b))

Modulo Arithmetic → (a+b)%m, (a×b)%m | Congruence: a≡b(mod m) | Fermat's little theorem

Chinese Remainder Theorem → Solve system of congruences x≡a₁(mod m₁), x≡a₂(mod m₂)... | mi pairwise coprime

Rabin-Karp → Hash-based string matching | Rolling hash | O(n+m) avg, O(nm) worst

KMP → Prefix-suffix table (failure function) | Never re-examines previous chars | O(n+m)

Boyer-Moore → Right-to-left scanning | Bad Character + Good Suffix heuristics | O(n/m) best case

Convex Hull → Smallest convex polygon containing all points | Graham Scan: O(n log n) | Jarvis March: O(nh)

1. Euclid's Algorithm for GCD

GCD (Greatest Common Divisor): Largest positive integer that divides both a and b without remainder.

Euclid's Key Insight: gcd(a, b) = gcd(b, a mod b)
Base Case: gcd(a, 0) = a
Time Complexity: O(log min(a, b)) — very fast!

Recursive Formula:

gcd(a, b) = a if b = 0
gcd(a, b) = gcd(b, a mod b) if b ≠ 0

Example: gcd(48, 18)
= gcd(18, 48 mod 18) = gcd(18, 12)
= gcd(12, 18 mod 12) = gcd(12, 6)
= gcd(6, 12 mod 6) = gcd(6, 0)
= 6

LCM: lcm(a, b) = (a × b) / gcd(a, b)

Solved Numerical

Q: Find GCD of 252 and 105 using Euclid's Algorithm. Show all steps.

Step-by-step:

gcd(252, 105): 252 = 2×105 + 42 → gcd(105, 42)
gcd(105, 42): 105 = 2×42 + 21 → gcd(42, 21)
gcd(42, 21): 42 = 2×21 + 0 → gcd(21, 0)
gcd(21, 0) = 21

Therefore: GCD(252, 105) = 21
LCM(252, 105) = (252 × 105) / 21 = 26460/21 = 1260

Verification: 252 = 21×12 ✓, 105 = 21×5 ✓

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;

// Recursive Euclid's GCD
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Iterative version (same logic)
int gcd_iter(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    cout << gcd(252, 105);  // Output: 21
}

2. Modulo Arithmetic

Modulo Operation: a mod m = remainder when a is divided by m.
Congruence: a ≡ b (mod m) means m divides (a - b), i.e., a and b have same remainder when divided by m.

Key Properties of Modular Arithmetic:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(a^n) mod m = ((a mod m)^n) mod m

Fermat's Little Theorem (p is prime, p ∤ a):
a^(p-1) ≡ 1 (mod p) → a^p ≡ a (mod p)
Use: Fast modular exponentiation, modular inverse

Modular Inverse: a⁻¹ mod m = a^(m-2) mod m (if m is prime)
i.e., a × a^(m-2) ≡ 1 (mod m)

💡 Examples:
• (17 + 8) mod 5 = ((17 mod 5) + (8 mod 5)) mod 5 = (2 + 3) mod 5 = 0
• (6 × 7) mod 5 = ((6 mod 5) × (7 mod 5)) mod 5 = (1 × 2) mod 5 = 2
• Fast: (2^10) mod 7 = ((2^5 mod 7)²) mod 7 = (32 mod 7)² mod 7 = 4² mod 7 = 16 mod 7 = 2

3. Chinese Remainder Theorem (CRT)

Chinese Remainder Theorem (CRT): If m₁, m₂, ..., mₙ are pairwise coprime (gcd(mᵢ, mⱼ)=1 for i≠j), then for any integers a₁, a₂, ..., aₙ, the system of congruences:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
⋮
x ≡ aₙ (mod mₙ)

has a unique solution modulo M = m₁ × m₂ × ... × mₙ.

CRT Algorithm:
1. Compute M = m₁ × m₂ × ... × mₙ
2. For each i: Mᵢ = M / mᵢ
3. Find yᵢ = Mᵢ⁻¹ mod mᵢ (modular inverse of Mᵢ w.r.t. mᵢ)
4. Solution: x = (Σ aᵢ × Mᵢ × yᵢ) mod M

Solved Numerical

Q: Solve: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Given: a₁=2, m₁=3 | a₂=3, m₂=5 | a₃=2, m₃=7
gcd(3,5)=1, gcd(3,7)=1, gcd(5,7)=1 → pairwise coprime ✓

M = 3 × 5 × 7 = 105
M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15

Find yᵢ (modular inverses):
y₁: 35 × y₁ ≡ 1 (mod 3) → 2y₁ ≡ 1 (mod 3) → y₁ = 2 (since 2×2=4≡1 mod 3)
y₂: 21 × y₂ ≡ 1 (mod 5) → 1×y₂ ≡ 1 (mod 5) → y₂ = 1 (since 21 mod 5 = 1)
y₃: 15 × y₃ ≡ 1 (mod 7) → 1×y₃ ≡ 1 (mod 7) → y₃ = 1 (since 15 mod 7 = 1)

x = (a₁×M₁×y₁ + a₂×M₂×y₂ + a₃×M₃×y₃) mod M
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105 = 23

Solution: x = 23
Verification: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓

4. Rabin-Karp String Matching Algorithm

Rabin-Karp Algorithm: Uses hashing to find pattern P in text T. Instead of comparing characters one by one, it computes a hash of the pattern and compares with hashes of each window of text. Uses rolling hash for efficient computation.

Time: O(n + m) average | O(nm) worst (hash collisions)
Space: O(1)

Algorithm:
1. Compute hash of pattern P (length m)
2. Compute hash of first window T[0..m-1]
3. Slide window: for i = 0 to n-m:
• If hash(T[i..i+m-1]) == hash(P): verify character by character (spurious hits possible!)
• Update rolling hash for next window: remove leftmost, add new rightmost character

Rolling Hash Formula:
hash(T[i+1..i+m]) = (d × (hash(T[i..i+m-1]) - T[i] × h) + T[i+m]) mod q
where d = alphabet size, h = d^(m-1) mod q, q = prime number

Solved Example

Q: Find pattern "26" in text "31415926535" using Rabin-Karp. Use d=10, q=11.

Pattern P = "26", m=2. Text T = "31415926535", n=11
h = d^(m-1) mod q = 10^1 mod 11 = 10
hash(P) = (2×10 + 6) mod 11 = 26 mod 11 = 4

Compute hash of each window:
window "31": (3×10+1) mod 11 = 31 mod 11 = 9 ≠ 4
window "14": rolling = (10×(9-3×10)+4) mod 11 = (10×(9-30)+4) mod 11 = ... = (10×(-21)+4) mod 11 = (-206) mod 11 = 3 ≠ 4
(continuing rolling hash for each window...)
window "26": hash = (2×10+6) mod 11 = 26 mod 11 = 4 = hash(P) → Match!
Verify: T[7..8] = "26" = P ✓

Pattern found at position 7!

5. KMP (Knuth-Morris-Pratt) Algorithm

KMP Algorithm: Preprocesses the pattern to build a failure function (partial match table) that avoids redundant comparisons. When a mismatch occurs, it uses the failure function to skip ahead rather than backtracking in the text.

Time: O(n + m) — O(m) preprocessing + O(n) matching
Key advantage: Never re-examines characters in the text (pointer never moves back)

Step 1 — Build Failure Function (LPS array):
LPS[i] = length of longest proper prefix of P[0..i] that is also a suffix.
(Proper prefix = prefix that is not the whole string)

Step 2 — Matching:
Use two pointers i (text) and j (pattern).
If P[j] == T[i]: advance both i and j
If j == m: pattern found at i-m, set j = LPS[j-1]
If mismatch and j > 0: j = LPS[j-1] (don't move i back!)
If mismatch and j == 0: move i forward

Solved Numerical — Build LPS Table

Q: Build LPS (failure function) for pattern P = "ABABCABAB". Then find P in T = "ABABDABABCABABCABAB".

Building LPS for P = "ABABCABAB":

Index: 0 1 2 3 4 5 6 7 8 Char: A B A B C A B A B LPS: 0 0 1 2 0 1 2 3 4 Explanation: P[0]='A': no proper prefix → LPS[0]=0 P[1]='B': "AB" → no prefix=suffix → LPS[1]=0 P[2]='A': "ABA" → "A" is prefix and suffix → LPS[2]=1 P[3]='B': "ABAB" → "AB" is prefix and suffix → LPS[3]=2 P[4]='C': "ABABC" → no prefix=suffix → LPS[4]=0 P[5]='A': "ABABCA" → "A" → LPS[5]=1 P[6]='B': "ABABCAB" → "AB" → LPS[6]=2 P[7]='A': "ABABCABA" → "ABA" → LPS[7]=3 P[8]='B': "ABABCABAB" → "ABAB" → LPS[8]=4

KMP Matching in T = "ABABDABABCABABCABAB":
When mismatch at T[4]='D' vs P[4]='C' (j=4): j = LPS[3]=2, restart from P[2]
Continue matching... Pattern found at position 9 and 14.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Build LPS (failure function)
vector<int> buildLPS(string pat) {
    int m = pat.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len-1];       // Backtrack in pattern only
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

// KMP Search
void KMPSearch(string text, string pat) {
    vector<int> lps = buildLPS(pat);
    int n=text.size(), m=pat.size(), i=0, j=0;
    while (i < n) {
        if (pat[j] == text[i]) { i++; j++; }
        if (j == m) {
            cout << "Found at index " << i-j << "\n";
            j = lps[j-1];
        } else if (i < n && pat[j] != text[i]) {
            if (j != 0) j = lps[j-1];
            else i++;
        }
    }
}

int main() {
    KMPSearch("ABABDABABCABABCABAB", "ABABCABAB");
    // Output: Found at index 9, Found at index 14 (... wait, adjusted)
}

6. Boyer-Moore Algorithm

Boyer-Moore Algorithm: The most efficient string matching algorithm in practice. Scans pattern from right-to-left and uses two heuristics to skip large portions of text.

Time: O(n/m) best case (sublinear!) | O(nm) worst case | O(n+m) preprocessing
Used in: Unix grep, text editors, DNA sequence matching

Two Heuristics:

1. Bad Character Heuristic:
On mismatch of T[i] with P[j]: find rightmost occurrence of T[i] in P. Shift pattern to align that character, or shift past T[i] if T[i] doesn't appear in P.
Shift = max(1, j - last_occurrence[T[i]])

2. Good Suffix Heuristic:
If suffix P[j+1..m-1] matched, find a previous occurrence of this suffix in P (or a matching prefix). Shift to align it with the matched portion of text.

Final shift = max(bad_character_shift, good_suffix_shift)

Solved Example

Q: Search for pattern "ABAAB" in text "ABAABABAAB" using Bad Character heuristic.

Bad Character Table for P = "ABAAB":
Last occurrence: A=3, B=4 (0-indexed from right: rightmost A at index 3, B at index 4)
More precisely: A appears at index 0,2,3 → rightmost=3; B appears at 1,4 → rightmost=4

Attempt 1: Align P[0..4] with T[0..4] = "ABAAB"
Compare right to left: P[4]='B', T[4]='B' ✓; P[3]='A', T[3]='A' ✓;
P[2]='A', T[2]='A' ✓; P[1]='B', T[1]='B' ✓; P[0]='A', T[0]='A' ✓
MATCH at position 0!

Attempt 2: Shift by 1, align P with T[1..5]="BAABA"
T[5]='A', P[4]='B' → Mismatch. T[5]='A' in P at index 3.
Shift = 4 - 3 = 1. Move to position 2.

Continue... MATCH at position 5! (T[5..9]="ABAAB")

Algorithm	Preprocessing	Best Case	Worst Case	Key Idea
Naive	O(1)	O(n)	O(nm)	Try all positions
Rabin-Karp	O(m)	O(n+m)	O(nm) (collisions)	Rolling hash
KMP	O(m)	O(n+m)	O(n+m)	Failure function, no backtrack
Boyer-Moore	O(m+σ)	O(n/m)	O(nm)	Right-to-left, skip using heuristics

7. Convex Hull

Convex Hull: The smallest convex polygon that contains all the given points. Think of it as the shape you get when you stretch a rubber band around all the points and let it snap.

Applications: Computer graphics, image processing, collision detection, pattern recognition, GIS systems

Algorithm 1: Graham Scan

Graham Scan Steps:
1. Find the point with lowest y-coordinate (leftmost if tie) — this is the pivot P₀
2. Sort remaining points by polar angle with respect to P₀ (counter-clockwise)
3. Push P₀ and P₁ onto stack
4. For each remaining point Pᵢ:
While top two points and Pᵢ make a clockwise turn (right turn): pop top
Push Pᵢ
5. Stack contains convex hull vertices

Time: O(n log n) — dominated by sorting
Space: O(n)

Algorithm 2: Jarvis March (Gift Wrapping)

Jarvis March Steps:
1. Start from leftmost point (guaranteed to be on hull)
2. Next hull point = point that makes smallest counter-clockwise angle from current
3. Repeat until back at start

Time: O(nh) where h = hull points. O(n²) worst case.
Best when: h is small (few hull points)

Cross Product — Key to Turn Detection

Cross Product of vectors AB and AC:
cross = (B.x - A.x) × (C.y - A.y) - (B.y - A.y) × (C.x - A.x)

cross > 0 → Counter-clockwise turn (left turn) — KEEP point C
cross = 0 → Collinear — points on same line
cross < 0 → Clockwise turn (right turn) — POP, not on hull

💡 Example:
Points: (0,0), (1,1), (2,0), (1,2), (0,2), (2,2)
Convex Hull: (0,0) → (2,0) → (2,2) → (0,2) → back to (0,0)
Interior point (1,1) and (1,2) are NOT on the hull.

Feature	Graham Scan	Jarvis March
Time	O(n log n)	O(nh) — O(n²) worst
Space	O(n)	O(n)
Method	Sort + stack-based	Gift wrapping — pick next one by one
Best when	General case	h (hull size) is small

⚡ Ready for Exam? Sab padh liya? Ab Quick Revision karo — formulas, key points, solved patterns aur exam tips ek jagah! Quick Revision Karo →

⚡Quick Revision — Last Minute Exam Prep!

📌 How to use: Read this 15 minutes before exam. Includes definitions, formulas, tricks, solved patterns — everything you need!

🗺️ Chapter 1 — Graph Algorithms

📖 Graph Representations:
Adjacency Matrix: V×V, O(V²) space, O(1) edge check → dense graphs
Adjacency List: O(V+E) space, O(deg) edge check → sparse graphs (preferred for traversal)

📌 Topological Sort — Key Points:
• Only works for DAG (Directed Acyclic Graph) — no cycles!
• DFS-based: push vertex to stack AFTER all descendants processed → reverse = topo order
• Kahn's: use in-degree array, enqueue when in-degree = 0
• If output size < V in Kahn's → cycle detected!

⚡ Dijkstra's Algorithm — Exam Formula:

dist[source] = 0, dist[others] = ∞
Greedy: always pick unvisited vertex with min dist[u]
Relax: if dist[u] + w(u,v) < dist[v] → update dist[v]

Time: O(V²) array | O(E log V) min-heap
⚠️ CANNOT handle negative weights!

✅ Bellman-Ford — Key Points:
• Relax ALL edges V-1 times
• Handles negative weights ✓, detects negative cycles ✓
• After V-1 iterations, if still updates → negative cycle exists!
• Time: O(V × E) — slower than Dijkstra

⚡ Floyd-Warshall — Core Formula (MEMORIZE!):

D[i][j] = min(D[i][j], D[i][k] + D[k][j]) for k = 1 to V

Initialize: D[i][j] = w(i,j) if edge exists | 0 if i=j | ∞ otherwise
Time: O(V³) | All-Pairs Shortest Path
Works with negative weights (not negative cycles)

🌲 Sollin's (Borůvka's) Algorithm — MST:
• Each component finds its CHEAPEST outgoing edge
• All cheapest edges added simultaneously → components merge
• Repeat until 1 component remains
• O(log V) phases → Time: O(E log V)
• Can be parallelized (unlike Kruskal's or Prim's)

Algorithm	Type	Handles -ve	Time	Approach
Dijkstra	Single Source SP	No ✗	O(V²)	Greedy
Bellman-Ford	Single Source SP	Yes ✓	O(VE)	DP
Floyd-Warshall	All-Pairs SP	Yes ✓	O(V³)	DP
Sollin's	MST	N/A	O(E log V)	Greedy parallel

⚙️ Chapter 2 — Computational Complexity

P vs NP — Definitions (IMP!):
P: Problems SOLVABLE in polynomial time O(n^k). "Easy" problems. Examples: sorting O(n log n), shortest path O(V²).

NP: Problems VERIFIABLE in polynomial time. P ⊆ NP (everything in P is also in NP).

NP-Hard: Every NP problem reduces to it in poly time. May not be in NP. Hardest problems.

NP-Complete: In NP AND NP-Hard. The hardest problems within NP. SAT was first NPC.

Proof Framework — NP-Complete:
1. Show X ∈ NP: given certificate, verify in poly time
2. Show X is NP-Hard: reduce known NPC Y → X in poly time (Y ≤p X)
→ X is NP-Complete ✓

💡 Key Relationships:
• P ⊆ NP (proven) → P problems are a subset of NP
• NP-Complete = NP ∩ NP-Hard
• If any NPC problem is in P → P = NP (unsolved, most believe P ≠ NP)
• Reduction: A ≤p B means "B is at least as hard as A"

🔤 Chapter 3 — Miscellaneous Topics

⚡ Euclid's GCD (MEMORIZE!):

gcd(a, b) = a if b = 0
gcd(a, b) = gcd(b, a mod b) otherwise

Time: O(log min(a, b))
lcm(a,b) = (a × b) / gcd(a, b)

Trace: gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6

📌 Modulo Arithmetic Rules:
(a+b) mod m = ((a mod m) + (b mod m)) mod m
(a×b) mod m = ((a mod m) × (b mod m)) mod m
Fermat: a^(p-1) ≡ 1 (mod p) for prime p, gcd(a,p)=1

🇨🇳 Chinese Remainder Theorem — Steps:
Given: x≡a₁(mod m₁), x≡a₂(mod m₂) ... (mᵢ pairwise coprime)
1. M = m₁ × m₂ × ...
2. Mᵢ = M/mᵢ
3. yᵢ = Mᵢ⁻¹ mod mᵢ (modular inverse)
4. x = (Σ aᵢ×Mᵢ×yᵢ) mod M

Algorithm	Preprocessing	Best Time	Worst Time	Key Technique
Naive	O(1)	O(n)	O(nm)	Try all positions
Rabin-Karp	O(m)	O(n+m)	O(nm)	Rolling hash
KMP	O(m) — LPS table	O(n+m)	O(n+m)	Failure function, no backtrack
Boyer-Moore	O(m+σ)	O(n/m)	O(nm)	Bad char + good suffix, right-to-left

✅ KMP LPS Table — Quick Trick:
LPS[i] = length of longest proper prefix of P[0..i] that is also its suffix.
P = "AABAAB": LPS = [0, 1, 0, 1, 2, 3]
P = "ABCABC": LPS = [0, 0, 0, 1, 2, 3]

Exam Tip: Show LPS computation step by step — build from left to right using two pointers.

📐 Convex Hull — Key Facts:
Graham Scan: O(n log n) — sort by polar angle + stack + cross product test
Jarvis March: O(nh) — gift wrapping, pick next by smallest angle
Cross product > 0: Left/CCW turn (keep) | < 0: Right/CW turn (pop)
Formula: (B.x-A.x)(C.y-A.y) - (B.y-A.y)(C.x-A.x)

⚠️ Common Exam Mistakes:
❌ Using Dijkstra for graphs with negative weights (use Bellman-Ford!)
❌ Applying topological sort on a graph with cycles
❌ Floyd-Warshall: forgetting to initialize diagonal as 0
❌ KMP: confusing LPS as "length-1" — it's the actual length of matching prefix-suffix
❌ NP-Complete proof: forgetting to show BOTH NP membership AND NP-hardness
❌ CRT: applying when moduli are NOT pairwise coprime
❌ Boyer-Moore: scanning pattern left-to-right (should be RIGHT-to-LEFT)

📄Previous Year Questions

Previous Year Question Paper Not Available Yet

Previous year question papers for this unit are not available yet. If you have the question paper, please share it through the contact page so it can be added for other students.

Share Question Paper

Design & Analysis of Algorithms

📚 Chapters

🗺️ Chapter 1 — Graph Algorithms

⚙️ Chapter 2 — Computational Complexity

🔤 Chapter 3 — Miscellaneous Topics

Previous Year Question Paper Not Available Yet