Data Structures and Algorithms for MCA — Complete Notes

Advanced Tree Structures

AVL Tree (Adelson-Velskii and Landis)

Self-balancing BST. Balance factor = height(left) - height(right) ∈ 1

Rotations to restore balance:

• Left Rotation (LL): Right child becomes new root
• Right Rotation (RR): Left child becomes new root
• Left-Right (LR): Left rotate left child, then right rotate
• Right-Left (RL): Right rotate right child, then left rotate

All operations O(log n) guaranteed

Red-Black Tree

Self-balancing BST used in Java TreeMap, C++ std::map.

Properties:

1. Every node is RED or BLACK
2. Root is BLACK
3. Leaves (NIL) are BLACK
4. RED node's children are BLACK
5. All paths from node to leaves have same number of BLACK nodes

All operations O(log n) but less rotations than AVL → better for insertions.

B-Tree (Multiway Tree)

Used in databases and file systems (MySQL uses B+ Tree).

Properties for B-Tree of order m:

• Every node has at most m children
• Minimum ⌈m/2⌉ children (except root)
• All leaves at same level
• Minimizes disk I/O

B+ Tree: All data in leaf nodes; internal nodes only for navigation; leaves linked for range queries.

Heap (Priority Queue)

Complete binary tree where parent ≥ children (max-heap) or parent ≤ children (min-heap).

Operations:

• Insert: Add at end, bubble up — O(log n)
• Extract max/min: Remove root, replace with last, bubble down — O(log n)
• Build heap from array: O(n) — not O(n log n)!

Heap Sort: Build max-heap, extract max n times → O(n log n)

Trie (Prefix Tree)

Tree where each path from root represents a string prefix. Used for: autocomplete, spell check, IP routing.

Operations: Insert, Search, StartsWith — all O(L) where L = string length

---

Hashing

Hash Function: Maps keys to array indices. Good hash function: Uniform distribution, fast to compute, deterministic.

Collision Resolution:

Open Addressing (Closed Hashing)

All elements stored in hash table itself.

• Linear Probing: h(k,i) = (h(k)+i) mod m — primary clustering problem
• Quadratic Probing: h(k,i) = (h(k)+c₁i+c₂i²) mod m — secondary clustering
• Double Hashing: h(k,i) = (h₁(k)+i×h₂(k)) mod m — best distribution

Separate Chaining (Open Hashing)

Each slot has a linked list of elements.

• Load factor α = n/m (n=elements, m=table size)
• Average successful search: 1 + α/2
• Keep α < 0.75 for good performance

Universal Hashing: Randomly select hash function → good average case.

---

String Algorithms

KMP (Knuth-Morris-Pratt) Pattern Matching

Finds all occurrences of pattern P in text T efficiently.

• Preprocess pattern to build failure function (prefix-suffix table)
• Time: O(n+m) vs naive O(nm)

Failure Function: For each position, length of longest proper prefix that is also suffix. Pattern "ABABC": failure = [0,0,1,2,0]

Rabin-Karp Algorithm

Uses hashing for pattern matching.

• Hash pattern, slide window over text computing rolling hash
• If hashes match, verify with direct comparison
• Time: O(n+m) average, O(nm) worst

Z-Algorithm

Z[i] = length of longest substring starting at position i that is also prefix of string. Time: O(n)

---

Advanced Graph Algorithms

Articulation Points and Bridges

Articulation point: Removing it disconnects the graph. Bridge: Removing it disconnects the graph. Found using DFS with discovery times and low values.

Strongly Connected Components (SCC)

Kosaraju's Algorithm:

1. Run DFS on original graph, record finish times
2. Transpose graph (reverse all edges)
3. Run DFS in decreasing finish time order

Tarjan's Algorithm: Single DFS pass using stack and low values.

Topological Sort

Linear ordering of vertices such that for every edge u→v, u comes before v. Conditions: Only valid for DAGs (Directed Acyclic Graphs)

Kahn's Algorithm (BFS-based):

1. Compute in-degree for all vertices
2. Add all 0 in-degree vertices to queue
3. Process queue: reduce neighbors' in-degrees, add new 0s to queue

Network Flow

Max-Flow Min-Cut Theorem: Maximum flow = Minimum cut capacity. Ford-Fulkerson: Find augmenting path, increase flow. O(E × max_flow). Edmonds-Karp (BFS-based Ford-Fulkerson): O(VE²)

---

Dynamic Programming — Advanced Problems

Longest Common Subsequence (LCS)

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[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[m][n]

Longest Increasing Subsequence (LIS)

O(n²) DP or O(n log n) with patience sorting/binary search.

Matrix Chain Multiplication

Find optimal parenthesization to minimize matrix multiplications. dp[i][j] = minimum multiplications for Aᵢ...Aⱼ dp[i][j] = min(dp[i][k] + dp[k+1][j] + pᵢ₋₁×pₖ×pⱼ) for all k from i to j-1

Edit Distance (Levenshtein Distance)

Minimum operations (insert, delete, replace) to convert string A to B.

if A[i]==B[j]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

---

Complexity Analysis

Amortized Analysis: Average time per operation over worst-case sequence.

• Dynamic array: O(1) amortized per append
• Splay tree: O(log n) amortized per operation

P vs NP:

• P: Problems solvable in polynomial time (sorting, shortest path)
• NP: Solutions verifiable in polynomial time (TSP, knapsack, SAT)
• NP-Complete: Hardest problems in NP (all NP problems reducible to it)
• NP-Hard: At least as hard as NP-Complete

Common NP-Complete Problems: SAT, 3-SAT, Vertex Cover, Clique, Hamilton Path, Travelling Salesman Decision.

---

Solved Problems

Q1 (MCA Entrance): What is the time complexity of building a heap from n elements? O(n) — not O(n log n). Heapify is called on n/2 nodes, but most nodes are near leaves (small subtrees). The mathematical sum converges to O(n).

Q2 (2023): Find LCS of "ABCBDAB" and "BDCAB". Build DP table systematically. LCS length = 4 ("BCAB" or "BDAB")

Q3 (2024): Prove that Dijkstra's algorithm doesn't work with negative weights. Counter-example: A→B cost 2, A→C cost 3, C→B cost -2. Dijkstra: B has cost 2. But A→C→B = 1 < 2. Dijkstra settles B too early before considering path through C.

---

Quick Revision Checklist

• AVL tree: balance factor ∈ 1, 4 rotations
• Red-Black: 5 properties, O(log n) all operations
• B-Tree: order m, minimum ⌈m/2⌉ children
• Heap: insert/extract O(log n), build O(n)
• KMP: O(n+m) pattern matching, failure function
• Open addressing: linear, quadratic, double hashing
• Load factor α = n/m; keep below 0.75
• SCC: Kosaraju (2 DFS) or Tarjan (1 DFS)
• Topological sort: only for DAGs, Kahn's algorithm
• LCS DP recurrence
• Edit distance DP recurrence
• P ⊆ NP, NP-Complete problems list