1.
Introduction
What is an algorithm?
Steps in algorithm design: input, output, correctness, efficiency.
Types of algorithms: deterministic, randomized, recursive, iterative.
Algorithmic problem-solving process.
Pseudocode and flow of control.
Time–space trade-offs.
Models of computation: RAM model, asymptotic reasoning.
Importance of algorithm design in competitive programming.
2. Efficiency
2.1 Time and Space
Time: number of basic operations.
Space: memory requirement (variables, recursion stacks, data structures).
Constants and hardware ignored in theoretical analysis.
2.2 Input Size
Running time depends on input size n.
Different inputs of same size can take different times → usually use worst-case
t(n).
How to define input size:
Arrays → number of elements.
Combinatorial problems → number of objects.
Graphs → vertices V and edges E.
Numbers → number of digits = ⌊log_b n⌋; arithmetic operations are digit-wise.
2.3 Choice of Basic Operations
Flexibility in defining “basic operation” (e.g., swaps vs assignments).
Asymptotic analysis ignores constant factors.
2.4 Orders of Magnitude
Focus on growth rates: log n, n, n log n, n², n³, 2ⁿ, n!.
Constants don’t matter; dominant term drives runtime.
2.5 Worst-Case and Average-Case Complexity
Worst Case: Maximum runtime over all inputs of size n; ensures upper bound.
Average Case: Expected runtime over a distribution of inputs; harder to compute.
Classification of worst-case inputs can reveal simpler subclasses with better
performance.
2.6 Amortized Analysis
Aggregate, accounting, potential methods.
Ensures overall efficiency over a sequence of operations.
2.7 Asymptotic Notations
Big O (O): Upper bound. t(n) ≤ c·g(n) for n ≥ n₀.
Big Omega (Ω): Lower bound. t(n) ≥ c·g(n) for n ≥ n₀.
Big Theta (Θ): Tight bound. t(n) = O(g(n)) and t(n) = Ω(g(n)).
Properties:
Sum of phases: f₁(n)+f₂(n) = O(max(g₁(n),g₂(n))).
Dominant term dictates asymptotic growth.
Use: Describes worst-case runtime, problem-level lower bounds, and asymptotic
optimality.
3. Searching
3.1 Linear Search
Scan all items sequentially.
Worst-case: O(N).
Works on unsorted arrays or lists.
3.2 Binary Search (Sorted Arrays)
Compare target K with middle element M:
K = M → found.
K < M → search left half.
K > M → search right half.
Stop when subarray is empty → not found.
Recurrence: T(0) = 1, T(n) = 1 + T(n/2) → O(log n).
Requires constant-time access (array indexing).
Concept: divide-and-conquer; each step halves search space.
Variants: search on monotonic functions, rotated sorted arrays, real numbers.
3.3 Hashing (overview)
Hash functions, collisions (chaining, open addressing).
Applications: sets, maps, frequency counting.
3.4 Search on Trees/Graphs
Depth-First Search (DFS).
Breadth-First Search (BFS).
Iterative deepening search.
4. Sorting
Comparison-based: Bubble, Insertion, Selection (O(n²)), Merge Sort (O(n log n)),
Quick Sort, Heap Sort.
Non-comparison: Counting Sort, Radix Sort, Bucket Sort.
Stability, custom comparators.
Inversions count, kth smallest/largest element (QuickSelect).
Sorting optimizations: IntroSort (C++ STL), Timsort (Python).
5. Basic Graph Algorithms
Graph representations: adjacency list, adjacency matrix, edge list.
BFS, DFS: traversal, connected components, path finding.
Cycle detection, topological sort (for DAGs), bipartite checking.
Connectivity: bridges, articulation points.
Trees: rooted/unrooted, traversal, diameter.
Union-Find / DSU: path compression, union by rank.
Applications: Kruskal’s MST, connectivity queries.
6. Dynamic Programming
Principle of Optimality.
Memoization vs Tabulation.
1D DP: Fibonacci, coin change, climbing stairs.
2D DP: Knapsack, subset sum, partition problem, LCS, LIS.
Grid DP: paths, min-cost path, obstacles.
String DP: edit distance, palindrome partitioning.
Tree DP: subtree properties, tree DP.
Bitmask DP: TSP, subset states.
Optimizations: space optimization, divide-and-conquer DP, convex hull trick.
Reconstruction: recovering solutions from DP tables.
7. Greedy Algorithms
Greedy-choice property and correctness proofs.
Classical problems: activity selection, fractional knapsack, job sequencing (Xerox
Shop), Huffman coding.
Minimum Spanning Tree: Prim’s, Kruskal’s.
Dijkstra’s shortest path (greedy + graph).
Matroid theory (conceptual).
Exchange argument for correctness.
Counterexamples where greedy fails.
8. Computing Shortest Paths
BFS for unweighted graphs.
Weighted graphs: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson (sparse graphs).
DAGs: topological order for shortest/longest paths.
Path reconstruction.
Negative weights and cycles.
Heuristic search (A*, D*) – introductory.
9. Heaps
Binary heap: min-heap, max-heap.
Operations: insertion, deletion, extract-min/max, heapify, build-heap (O(n)).
Priority queue implementation.
Applications: Dijkstra, heap sort, median maintenance (two heaps).
Other heaps (conceptual): Fibonacci heap, binomial heap.
10. Permutations
Factorial number system: ranking/unranking.
Next/previous permutation algorithms.
Generate all permutations recursively/iteratively.
Permutation-based search: N-Queens, TSP, assignment problems.
Backtracking, lexicographic ordering.
Counting distinct permutations with duplicates.
11. Directed Acyclic Graphs (DAGs)
Topological sorting: Kahn’s algorithm, DFS-based.
Detect cycles.
Shortest and longest paths in DAGs.
DP on DAGs.
Applications: job scheduling, dependency resolution, critical path method, SCC
condensation.
12. Computing Prefix Sums
1D: cumulative sums, range sum queries O(1) after preprocessing.
2D: submatrix sums.
Difference arrays for range updates.
Applications: frequency counting, sliding window optimization, prefix XOR, prefix
GCD.
13. Sliding Window Algorithms
Fixed window: max/min in subarray, counting distinct elements.
Variable window: longest substring with k distinct chars, smallest subarray with
sum ≥ target.
Deque-based optimization → O(n).
Two-pointer equivalence.
Applications: subarray sums, histogram, submatrix problems, Kadane’s algorithm,
moving averages.
14. Document Similarity & Edit Distance
Plagiarism detection, version diff, web search relevance.
Minimum edit operations: insert, delete, replace.
Brute force vs recursive decomposition.
Inefficiency of naive recursion.
DP to avoid recomputation of subproblems.
Variations: word-level similarity, ignoring word order, topic-based dictionaries.