Algorithm Summary Notes
Union-Find Algorithm
Union-Find Algorithm (Disjoint Set Union - DSU)
Purpose:
Efficiently manages a partition of a set into disjoint subsets, mainly used for detecting cycles and finding
connected components in a graph.
Key Operations:
- MakeSet(x): Initializes a set with one element.
- Find(x): Returns the representative (root) of the set containing x with path compression.
- Union(x, y): Unites the sets containing x and y using union by rank.
Time Complexity:
- Without optimizations: O(n) per operation.
- With path compression or union by rank: O(log n) per operation.
- With both optimizations: O((n)) per operation, where (n) is the inverse Ackermann function (very
slow-growing).
Pseudocode:
Algorithm MakeSet(x):
parent[x] = x
rank[x] = 0
Algorithm Find(x):
if parent[x] != x:
parent[x] = Find(parent[x]) // Path Compression
return parent[x]
Algorithm Union(x, y):
rootX = Find(x)
rootY = Find(y)
Algorithm Summary Notes
if rootX != rootY:
if rank[rootX] < rank[rootY]:
parent[rootX] = rootY
elif rank[rootX] > rank[rootY]:
parent[rootY] = rootX
else:
parent[rootY] = rootX
rank[rootX] = rank[rootX] + 1
Heap (Min-Heap Example)
Heap (Min-Heap Example)
Purpose:
A tree-based structure where the parent node maintains a specific order relation with children (min-heap or
max-heap).
Time Complexity:
- Insertion: O(log n)
- Deletion (of root): O(log n)
- Finding min/max: O(1)
- Heapify (build heap from array): O(n)
Pseudocode:
Algorithm MinHeapify(A, i, heapSize):
left = 2*i + 1
right = 2*i + 2
smallest = i
if left < heapSize and A[left] < A[smallest]:
smallest = left
if right < heapSize and A[right] < A[smallest]:
smallest = right
Algorithm Summary Notes
if smallest != i:
swap A[i] and A[smallest]
MinHeapify(A, smallest, heapSize)
Algorithm Insert(A, key, heapSize):
heapSize = heapSize + 1
i = heapSize - 1
A[i] = key
while i > 0 and A[parent(i)] > A[i]:
swap A[i] and A[parent(i)]
i = parent(i)
Algorithm ExtractMin(A, heapSize):
if heapSize < 1:
error "Heap underflow"
min = A[0]
A[0] = A[heapSize - 1]
heapSize = heapSize - 1
MinHeapify(A, 0, heapSize)
return min
Algorithm BuildMinHeap(A, n):
heapSize = n
for i from floor(n/2) down to 0:
MinHeapify(A, i, heapSize)
function parent(i):
return floor((i-1)/2)
Divide and Conquer
Divide and Conquer
Algorithm Summary Notes
Purpose:
An algorithmic paradigm that recursively breaks a problem into subproblems until they become simple
enough to solve directly. The solutions to the subproblems are then combined.
Recurrence Relation:
T(n) = aT(n/b) + f(n)
Where:
- T(n): time for input of size n
- a: number of subproblems
- n/b: size of each subproblem
- f(n): work done outside recursive calls
Time Complexity Examples:
- Merge Sort: T(n)=2T(n/2)+O(n) O(n log n)
- Quick Sort (average): T(n)=2T(n/2)+O(n) O(n log n)
- Binary Search: T(n)=T(n/2)+O(1) O(log n)
Pseudocode:
Algorithm DivideAndConquer(problem):
if problem is small enough to solve directly:
return SolveDirectly(problem)
else:
subproblems = Divide(problem)
subsolutions = [DivideAndConquer(sub) for sub in subproblems]
return Combine(subsolutions)
Algorithm SolveDirectly(problem):
// Base case: solve the small problem
Algorithm Divide(problem):
// Break the problem into smaller subproblems
Algorithm Summary Notes
Algorithm Combine(subsolutions):
// Combine the solutions of the subproblems
