1.1 What Is an Algorithm? 1.2 Historical Evolution of Algorithms 1.3 Role in Computer Science and Engineering 1.4 Algorithmic Thinking 1.5 Correctness vs Efficiency 1.6 Real-World Case Studies 1.7 Algorithm Engineering 1.8 Overview of Data Structures 1.9 Course Roadmap
2.1 Mathematical Proof Techniques • Direct Proof • Contradiction • Induction • Strong Induction
2.2 Asymptotic Analysis • Big-O • Big-Ω • Big-Θ • Little-o and Little-ω
2.3 Recurrences • Substitution Method • Recursion Tree • Master Theorem • Akra–Bazzi Method
2.4 Logarithms and Exponentials 2.5 Summations and Series 2.6 Combinatorics 2.7 Probability Theory 2.8 Random Variables and Expectations 2.9 Linear Algebra Basics 2.10 Number Theory Foundations
3.1 Time Complexity 3.2 Space Complexity 3.3 Worst, Average, Best Case 3.4 Amortized Analysis • Aggregate Method • Accounting Method • Potential Method
3.5 Lower Bounds 3.6 Decision Trees 3.7 Information-Theoretic Bounds 3.8 Empirical Performance Analysis 3.9 Cache Complexity 3.10 Parallel Complexity (PRAM Model)
4.1 Memory Layout 4.2 Static vs Dynamic Arrays 4.3 Resizing Strategies 4.4 Multi-Dimensional Arrays 4.5 Cache Locality 4.6 Sparse Arrays
5.1 Singly Linked Lists 5.2 Doubly Linked Lists 5.3 Circular Lists 5.4 Skip Lists 5.5 Memory Allocation Issues
6.1 Stack Implementations 6.2 Applications (DFS, Expression Parsing) 6.3 Queue Implementations 6.4 Circular Queues 6.5 Deques 6.6 Priority Queues
7.1 Hash Functions 7.2 Collision Resolution • Chaining • Open Addressing • Linear Probing • Quadratic Probing • Double Hashing
7.3 Universal Hashing 7.4 Perfect Hashing 7.5 Cuckoo Hashing 7.6 Bloom Filters 7.7 Consistent Hashing
8.1 Tree Terminology 8.2 Binary Trees 8.3 Tree Traversals 8.4 Expression Trees 8.5 Threaded Trees 8.6 General Trees
9.1 BST Properties 9.2 Insert/Delete/Search 9.3 Complexity Analysis 9.4 Augmented BSTs
10.1 AVL Trees 10.2 Red-Black Trees 10.3 Splay Trees 10.4 Treaps 10.5 B-Trees 10.6 B+ Trees 10.7 2-3 Trees 10.8 AA Trees
11.1 Binary Heap 11.2 d-ary Heap 11.3 Fibonacci Heap 11.4 Binomial Heap 11.5 Pairing Heap 11.6 Soft Heap
12.1 Bubble Sort 12.2 Selection Sort 12.3 Insertion Sort 12.4 Stability and Adaptiveness
13.1 Merge Sort 13.2 Quick Sort 13.3 Heap Sort 13.4 Introsort 13.5 TimSort
14.1 Counting Sort 14.2 Radix Sort 14.3 Bucket Sort
15.1 Randomized Selection 15.2 Median of Medians 15.3 Order Statistics
16.1 Linear Search 16.2 Binary Search 16.3 Interpolation Search 16.4 Exponential Search 16.5 Ternary Search
17.1 Trie 17.2 Compressed Trie 17.3 Suffix Trees 17.4 Suffix Arrays 17.5 Aho-Corasick Automaton
18.1 Range Queries 18.2 Lazy Propagation 18.3 2D Segment Trees 18.4 Binary Indexed Trees
19.1 Basic Implementation 19.2 Path Compression 19.3 Union by Rank 19.4 Applications
20.1 Partial Persistence 20.2 Full Persistence 20.3 Functional Data Structures
21.1 Adjacency List 21.2 Adjacency Matrix 21.3 Incidence Matrix
22.1 BFS 22.2 DFS 22.3 Topological Sorting 22.4 Connected Components
23.1 Dijkstra’s Algorithm 23.2 Bellman-Ford 23.3 Floyd-Warshall 23.4 Johnson’s Algorithm 23.5 A* Search
24.1 Kruskal’s Algorithm 24.2 Prim’s Algorithm 24.3 Borůvka’s Algorithm
25.1 Ford-Fulkerson 25.2 Edmonds-Karp 25.3 Dinic’s Algorithm 25.4 Push-Relabel 25.5 Min-Cost Flow 25.6 Max-Flow Min-Cut Theorem
26.1 Strongly Connected Components 26.2 Bipartite Matching 26.3 Hungarian Algorithm 26.4 Graph Coloring 26.5 Planar Graphs 26.6 Eulerian and Hamiltonian Paths
27.1 Strategy 27.2 Master Theorem 27.3 Applications
28.1 Greedy Choice Property 28.2 Activity Selection 28.3 Huffman Coding 28.4 Matroid Theory
29.1 Memoization 29.2 Tabulation 29.3 Knapsack 29.4 Longest Common Subsequence 29.5 Matrix Chain Multiplication 29.6 DP Optimization Techniques
30.1 N-Queens 30.2 Subset Sum 30.3 Constraint Satisfaction
31.1 Bounding Strategies 31.2 Traveling Salesman Problem
32.1 Las Vegas vs Monte Carlo 32.2 Randomized QuickSort 32.3 Randomized Min Cut
33.1 Approximation Ratios 33.2 Vertex Cover 33.3 Set Cover
34.1 KMP 34.2 Rabin-Karp 34.3 Z Algorithm 34.4 Boyer-Moore
35.1 Convex Hull 35.2 Line Sweep 35.3 Closest Pair
36.1 PRAM 36.2 MapReduce 36.3 Parallel Sorting 36.4 Distributed Graph Processing
37.1 I/O Model 37.2 B-Tree Optimization 37.3 Cache-Oblivious Algorithms
38.1 Count-Min Sketch 38.2 Bloom Filters 38.3 Reservoir Sampling
39.1 RSA 39.2 ECC 39.3 Hashing Algorithms
40.1 P vs NP 40.2 NP-Complete Problems 40.3 Reductions 40.4 Cook-Levin Theorem 40.5 PSPACE
41.1 Performance Profiling 41.2 Memory Optimization 41.3 Cache-Aware Design 41.4 Benchmarking
42.1 Formal Verification 42.2 Property-Based Testing 42.3 Fuzzing Algorithms
43.1 Search Engines 43.2 Database Indexing 43.3 Blockchain Structures 43.4 Operating Systems Scheduling
A. Mathematical Tables B. Complexity Classes Reference C. Common Algorithm Patterns D. Interview Problem Patterns E. Competitive Programming Guide F. Bibliography G. Index
An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically designed to perform a specific task or solve a particular class of problems. At its essence, an algorithm transforms input data into output results through a series of computational steps. This definition encompasses everything from simple recipes for sorting a list of numbers to complex procedures for machine learning and cryptographic protocols.
The term "algorithm" derives from the name of the Persian mathematician Muhammad ibn Musa al-Khwarizmi, whose 9th-century work on arithmetic and algebra laid foundational concepts for systematic problem-solving. Today, algorithms form the intellectual core of computer science, representing the procedural knowledge that enables computation.
Every algorithm must satisfy several fundamental properties:
Finiteness: An algorithm must always terminate after a finite number of steps. This does not mean it must be fast, but it cannot run forever. Consider an algorithm that computes the greatest common divisor of two numbers—it will eventually reach zero and terminate, whereas a procedure that keeps generating random numbers hoping to find a specific value might never terminate.
Definiteness: Each step must be precisely defined and unambiguous. The actions to be taken must be specified clearly for each case. For example, "add 1 to x" is definite, while "set x to approximately y+1" is not, because "approximately" has no precise computational meaning.
Input: An algorithm may have zero or more inputs, taken from specified sets of objects. A sorting algorithm takes an unsorted sequence as input; a random number generator might take no input at all.
Output: An algorithm produces one or more outputs, which bear a specified relationship to the inputs. The relationship defines what the algorithm accomplishes—for sorting, the output must be a permutation of the input that is non-decreasing.
Effectiveness: All operations must be sufficiently basic that they can, in principle, be performed exactly and in finite time by a human using pencil and paper. While modern computers extend our capabilities, the principle ensures algorithmic steps are mechanically realizable.
Consider a simple example: the Euclidean algorithm for finding the greatest common divisor (GCD) of two non-negative integers a and b:
function GCD(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return a
This algorithm satisfies all properties: it terminates because the second argument strictly decreases in each iteration; each step is definite (modulo operation, assignment); it takes two inputs; it outputs their GCD; and all operations are basic arithmetic.
The history of algorithms spans millennia, evolving from ancient mathematical procedures to the sophisticated constructs that power modern computing. Understanding this evolution provides insight into both the nature of algorithmic thinking and the forces that shaped its development.
Ancient Foundations (3000 BCE - 500 CE) : The earliest known algorithms appeared in ancient Mesopotamia, where clay tablets documented procedures for arithmetic operations, solving quadratic equations, and computing interest. Egyptian mathematics, preserved in the Rhind Mathematical Papyrus (circa 1650 BCE), contained algorithms for multiplication and division using doubling and halving—techniques that foreshadowed modern binary arithmetic.
Euclid's Elements (circa 300 BCE) contained the first known non-trivial algorithm: the Euclidean algorithm for computing greatest common divisors. This algorithm remains significant not only for its practical utility but because it demonstrated that mathematical knowledge could be expressed as systematic procedures. The algorithm's elegance—repeatedly replacing larger numbers with their remainders—exemplifies algorithmic thinking that transcends cultural boundaries.
Greek mathematicians also developed the Sieve of Eratosthenes for finding prime numbers and algorithms for approximating square roots. These early algorithms shared a common characteristic: they were expressed in natural language and mathematical notation, intended for human execution.
Medieval and Islamic Contributions (500-1500) : The Islamic Golden Age witnessed systematic study of algorithmic methods. Al-Khwarizmi's work "On the Calculation with Hindu Numerals" (825 CE) introduced the decimal positional system to the Western world and detailed procedures for arithmetic operations. His name, Latinized as "Algoritmi," eventually gave us the word "algorithm."
Persian mathematician Al-Kashi calculated π to 16 decimal places using innovative algorithms in the 15th century. Meanwhile, Chinese mathematicians developed the fangcheng method for solving linear systems, equivalent to Gaussian elimination, centuries before its rediscovery in Europe.
The Rise of Mechanical Computation (1600-1900) : The 17th century saw the first mechanical calculating devices. Wilhelm Schickard's Calculating Clock (1623) and Blaise Pascal's Pascaline (1642) automated arithmetic operations. Gottfried Wilhelm Leibniz developed the Step Reckoner and envisioned a universal logical calculus—the characteristica universalis—that would enable mechanical reasoning.
Charles Babbage's Analytical Engine (1837) represented a watershed moment. Though never completed, its design incorporated fundamental algorithmic concepts: conditional branching, loops, and separate storage and processing units. Ada Lovelace, often credited as the first programmer, recognized that such a machine could process not just numbers but any symbols according to rules—the essence of general-purpose computation.
Formal Foundations (1900-1945) : The early 20th century witnessed foundational crises in mathematics, prompting investigations into the nature of computation itself. David Hilbert's Entscheidungsproblem asked whether there existed a mechanical procedure to determine the truth of mathematical statements. This question catalyzed work by Alan Turing, Alonzo Church, Kurt Gödel, and Emil Post.
Alan Turing's 1936 paper "On Computable Numbers" introduced the Turing machine—an abstract model of computation that captured the intuitive notion of algorithmic procedure. Turing argued convincingly that any function computable by a human following a mechanical procedure could be computed by his machine. This Church-Turing thesis established the theoretical boundaries of algorithmic computation.
During World War II, algorithmic thinking proved crucial for code-breaking. Turing's work at Bletchley Park involved developing algorithms for decrypting Enigma messages, combining theoretical insight with practical engineering constraints.
The Computer Age (1945-Present) : The development of stored-program computers in the late 1940s transformed algorithms from human-executed procedures into machine-executable code. John von Neumann's architecture separated algorithm (program) from data, enabling computers to modify their own programs—a capability with profound implications.
The 1950s and 1960s saw the emergence of algorithm analysis as a discipline. Donald Knuth's monumental "The Art of Computer Programming," begun in 1962, systematized knowledge about algorithms and their analysis. Edsger Dijkstra's work on shortest paths (1956) and his subsequent contributions to structured programming shaped both theory and practice.
The complexity classes P and NP were formalized in the 1970s, establishing a framework for understanding algorithmic difficulty. Stephen Cook's 1971 paper introduced NP-completeness, showing that thousands of seemingly different problems were computationally equivalent in a precise sense.
Recent decades have witnessed algorithmics expanding into every domain: randomized algorithms that use coin flips to achieve efficiency, approximation algorithms for NP-hard problems, online algorithms that process streaming data, and quantum algorithms that exploit quantum mechanical effects.
Algorithms occupy a central position in computer science and engineering, serving as the conceptual bridge between problem specification and computational solution. Their role manifests across multiple dimensions:
Theoretical Foundation: Algorithms provide a precise language for describing computational processes. Complexity theory classifies problems based on the resources required for algorithmic solution, establishing inherent limits on what computers can achieve. The P versus NP question, perhaps the most important open problem in computer science, concerns whether efficient algorithms exist for a vast class of practically important problems.
System Design: Every software system embodies algorithms at multiple levels. Operating systems use scheduling algorithms to allocate processor time, memory management algorithms to handle allocation and garbage collection, and file system algorithms to organize persistent storage. Database systems implement sophisticated algorithms for query optimization, transaction management, and index maintenance. Network protocols rely on routing algorithms, congestion control, and error detection.
Application Development: Domain-specific algorithms enable countless applications. Search engines use ranking algorithms, indexing structures, and crawling strategies. Computer graphics relies on rendering algorithms, hidden surface removal, and geometric transformations. Cryptographic protocols implement encryption algorithms, digital signatures, and key exchange mechanisms. Machine learning systems are essentially collections of optimization algorithms, gradient descent methods, and statistical inference procedures.
Performance Engineering: Understanding algorithms is essential for building efficient systems. The difference between O(n²) and O(n log n) algorithms becomes critical at scale—sorting a million items might take seconds versus hours. Engineers must choose appropriate data structures and algorithms based on access patterns, memory hierarchies, and performance requirements.
Intellectual Discipline: Algorithmic thinking—the ability to formulate problems as computational procedures and reason about their properties—represents a fundamental mode of thought applicable beyond computer science. Biologists use sequence alignment algorithms to compare DNA; physicists employ simulation algorithms to model complex systems; financial analysts utilize algorithmic trading strategies.
Algorithmic thinking encompasses a set of cognitive skills and conceptual frameworks essential for designing, analyzing, and implementing algorithms. Developing this mode of thought requires practice with specific patterns of reasoning:
Decomposition: Complex problems must be broken into manageable subproblems. A sorting algorithm might decompose into divide, conquer, and combine phases. A pathfinding algorithm might separate graph traversal from distance calculation. Effective decomposition respects the natural structure of the problem while enabling efficient solution.
Abstraction: Essential details must be distinguished from incidental ones. When analyzing a sorting algorithm, we abstract away from specific processor speeds or memory hierarchies to focus on fundamental operations and their frequencies. When designing a data structure, we specify interfaces without committing to implementations.
Pattern Recognition: Many problems share structural similarities that admit common algorithmic approaches. Recognizing that a scheduling problem resembles interval partitioning suggests greedy algorithms. Seeing that a combinatorial optimization exhibits optimal substructure points toward dynamic programming. The experienced algorithm designer maintains a repertoire of canonical problems and their solutions.
Invariant Reasoning: Identifying invariants—properties that remain true throughout algorithm execution—provides a powerful tool for understanding and proving correctness. Loop invariants help reason about iterative algorithms; data structure invariants ensure consistent state after operations.
Trade-off Analysis: Algorithm design inevitably involves trade-offs between competing objectives: time versus space, worst-case versus average-case performance, simplicity versus efficiency, generality versus specialization. Recognizing these trade-offs and making appropriate choices characterizes mature algorithmic judgment.
Case Study: Binary Search
Consider binary search in a sorted array—a canonical illustration of algorithmic thinking. The problem: determine whether a target value exists in a sorted array of n elements. The naive approach scans sequentially, requiring up to n comparisons. Binary search achieves O(log n) comparisons by exploiting the sorted property.
The algorithm maintains an invariant: if the target exists, it lies within the current interval [low, high]. Initially, this interval covers the entire array. At each step, we examine the middle element. If it equals the target, we succeed. If the target is smaller, we continue searching the left half; if larger, the right half. The invariant ensures correctness, and halving the interval guarantees logarithmic steps.
This simple algorithm exemplifies algorithmic thinking: recognizing that sorted order enables more efficient search, decomposing the problem into repeated halving, maintaining an invariant to guide reasoning, and analyzing the trade-off between preprocessing (sorting) and query efficiency.
Algorithm design confronts a fundamental tension: algorithms must be both correct and efficient. These objectives sometimes align but often compete, requiring careful balancing.
Correctness: An algorithm is correct if, for every valid input, it terminates and produces the expected output. Establishing correctness requires rigorous reasoning:
- Partial correctness: If the algorithm terminates, it produces correct output
- Total correctness: The algorithm always terminates and produces correct output
Proving correctness typically involves:
- Preconditions: Conditions that must hold before algorithm execution
- Postconditions: Conditions that must hold after algorithm execution
- Invariants: Properties preserved throughout execution
- Variants: Measures that ensure termination by decreasing in each iteration
Consider insertion sort. The outer loop maintains the invariant that elements before the current position are sorted. Initially, this holds vacuously for the first element. Each iteration inserts the next element into its proper place among the sorted prefix, preserving the invariant. When the loop completes, the entire array is sorted. Termination follows because the loop processes each element exactly once.
Efficiency: Efficiency concerns resource consumption, typically time and space. Algorithm analysis quantifies efficiency through complexity measures that abstract away from specific implementations:
- Time complexity: Number of basic operations as function of input size
- Space complexity: Amount of memory required as function of input size
- Asymptotic analysis: Behavior as input size grows large
The efficiency-correctness relationship manifests in several ways:
Correct but inefficient: A correct algorithm may be practically useless if its resource requirements exceed available capacity. Computing all permutations to sort a list is correct but infeasible for lists of moderate size.
Efficient but incorrect: An algorithm that produces wrong answers quickly is worse than useless—it may lead to incorrect decisions based on faulty results. Many subtle bugs arise from "optimizations" that violate correctness conditions.
Trade-offs: Sometimes correctness can be relaxed in controlled ways to gain efficiency. Randomized algorithms may produce incorrect results with tiny probability; approximation algorithms guarantee near-optimal solutions; online algorithms must make decisions without full information.
The interplay between correctness and efficiency shapes algorithm design. Dijkstra's shortest path algorithm achieves efficiency through careful data structure choices while maintaining correctness through invariants. Quicksort's efficiency depends on pivot selection, but correctness requires handling all cases regardless of pivot quality.
Examining how algorithms operate in practical contexts illuminates their importance and the considerations that arise in real applications.
Case Study 1: Google Search
When a user enters a query, Google's algorithms execute within milliseconds to return relevant results. The process involves multiple algorithmic components:
-
Crawling: Web crawlers traverse the internet, following links and downloading pages. The crawler must prioritize which pages to visit, respect robots.txt protocols, and avoid overloading servers—a graph traversal problem with resource constraints.
-
Indexing: Downloaded pages are processed to build inverted indices mapping terms to documents. This involves parsing HTML, eliminating stop words, stemming terms, and storing positional information. The data structure must support fast lookups while managing petabytes of data.
-
Ranking: The PageRank algorithm, originally developed by Larry Page and Sergey Brin, evaluates page importance based on link structure. Pages receive higher rank if linked by many important pages—a recursive definition solved through iterative computation akin to eigenvector calculation. Modern ranking combines hundreds of signals using machine learning models.
-
Query processing: The query is parsed, expanded with related terms, and matched against the index. Results are ranked, filtered, and formatted with snippets showing query context. All this must happen within subsecond latency while handling millions of concurrent queries.
Case Study 2: GPS Navigation
Navigation apps like Google Maps or Waze solve the shortest path problem on road networks with millions of nodes. The algorithmic challenges include:
-
Graph representation: Road networks are represented as graphs with weighted edges representing travel time or distance. Turn restrictions, one-way streets, and traffic conditions add complexity.
-
Pathfinding: Dijkstra's algorithm provides a foundation, but practical implementations use optimizations: bidirectional search expands from both start and destination; A* uses heuristics to guide search; contraction hierarchies preprocess networks for faster queries.
-
Traffic prediction: Real-time traffic data and historical patterns inform edge weights. Machine learning algorithms predict future congestion based on time of day, weather, and special events.
-
Alternative routes: Users often want multiple route options. Finding diverse yet reasonable paths requires specialized algorithms that avoid excessive overlap.
-
Map matching: GPS coordinates must be matched to road segments despite noise and sampling errors—a problem solved using hidden Markov models or geometric algorithms.
Case Study 3: Netflix Recommendation System
Netflix's recommendation engine suggests content users might enjoy, driving significant engagement. The algorithmic foundation includes:
-
Collaborative filtering: Users with similar viewing histories receive similar recommendations. Matrix factorization techniques decompose the user-item interaction matrix into latent factors representing preferences and item characteristics.
-
Content-based filtering: Item attributes (genre, cast, director) inform recommendations. Natural language processing extracts features from descriptions and reviews.
-
Bandit algorithms: New users present exploration-exploitation dilemmas: should the system recommend known popular items or try diverse options to learn preferences? Multi-armed bandit algorithms balance these objectives.
-
Online learning: Recommendation models update continuously as new data arrives, requiring algorithms that adapt incrementally rather than retraining from scratch.
Case Study 4: Airline Ticketing Systems
Airline reservation systems handle millions of queries daily, pricing itineraries across complex fare rules. The algorithmic challenges include:
-
Graph algorithms: Route finding between cities with connecting flights requires shortest path algorithms adapted for schedule constraints.
-
Dynamic programming: Fare calculation involves nested rule structures—booking classes, advance purchase requirements, minimum stay constraints—processed through recursive algorithms that explore valid fare combinations.
-
Inventory management: Seat availability updates in real-time as bookings occur and fares change. Consistent views across distributed systems require careful transaction management.
-
Optimization: Revenue management algorithms dynamically adjust prices based on demand forecasts, overbooking probabilities, and competitive positioning.
These case studies illustrate common themes: algorithms rarely exist in isolation but combine multiple techniques; real-world constraints (scale, latency, reliability) shape algorithmic choices; and theoretical foundations enable practical solutions while practical requirements inspire theoretical advances.
Algorithm engineering bridges the gap between theoretical algorithm design and practical implementation. While theoretical analysis provides asymptotic guarantees, actual performance depends on myriad factors: cache behavior, memory hierarchy, parallelization opportunities, and implementation details.
The Algorithm Engineering Cycle: Developing practical algorithms involves iterative refinement through several phases:
-
Design: Based on problem requirements and theoretical knowledge, propose algorithmic approaches. Consider both classical solutions and novel adaptations.
-
Analysis: Derive theoretical properties—correctness, complexity bounds, resource requirements. Identify potential bottlenecks and worst-case scenarios.
-
Implementation: Translate the algorithm into efficient code. Choose appropriate data structures, optimize memory layout, exploit hardware features.
-
Experimentation: Measure performance on representative inputs. Profile to identify bottlenecks, compare alternatives, validate theoretical predictions.
-
Refinement: Based on experimental results, modify the algorithm or implementation to improve performance. Return to analysis to ensure modifications preserve correctness.
This cycle recognizes that theoretical and practical considerations mutually inform each other. A theoretically optimal algorithm may perform poorly due to constant factors or cache effects; a theoretically inferior algorithm might excel in practice for typical inputs.
Performance Factors Beyond Asymptotics:
-
Constant factors: An O(n log n) algorithm with high constant factors may underperform an O(n²) algorithm for problem sizes encountered in practice.
-
Memory hierarchy: Modern computers have multiple cache levels, main memory, and disk. Algorithms that exhibit locality of reference outperform those with random access patterns, even with similar operation counts.
-
Branch prediction: Conditional branches that are hard to predict can stall pipelines. Data structures and algorithms that minimize unpredictable branches often perform better.
-
Vectorization: SIMD instructions process multiple data elements simultaneously. Algorithms amenable to vectorization can achieve substantial speedups.
-
Parallelism: Multi-core processors enable parallel execution. Algorithms must be designed to expose parallelism and manage synchronization overhead.
Implementation Techniques:
-
Data structure selection: Choosing appropriate data structures dramatically affects performance. A red-black tree provides guaranteed O(log n) operations, but a hash table may offer O(1) expected time with suitable hash functions.
-
Memory management: Custom allocators, object pooling, and cache-aware layout reduce allocation overhead and improve locality.
-
Algorithmic variants: Hybrid algorithms combine approaches to leverage strengths. Introsort begins with quicksort, switches to heapsort if recursion depth exceeds threshold, and uses insertion sort for small subproblems.
-
Tuning parameters: Many algorithms have parameters (e.g., pivot selection in quicksort, resize factor in dynamic arrays) that affect performance. Empirical tuning identifies optimal settings for specific environments.
Case Study: Sorting in Practice
Theoretical sorting literature describes numerous algorithms with various asymptotic guarantees. Practical sorting, however, relies on carefully engineered implementations:
-
Timsort, used in Python and Java, combines merge sort and insertion sort. It exploits natural runs in data, achieving O(n log n) worst-case but often linear performance on partially sorted inputs.
-
Dual-pivot quicksort, used in Java's Arrays.sort, selects two pivots and partitions into three segments. Analysis shows reduced number of comparisons compared to single-pivot variants.
-
Radix sort outperforms comparison-based sorts for fixed-length integer keys, despite theoretical O(n) complexity being "worse" than O(n log n) by asymptotic standards—the constant factors favor radix sort for practical n.
These examples demonstrate algorithm engineering: theoretical understanding guides design, but practical considerations determine the final implementation.
Data structures organize and store data to enable efficient access and modification. The relationship between algorithms and data structures is symbiotic—algorithms operate on data structures, and data structure design anticipates algorithmic requirements.
Fundamental Data Structure Categories:
-
Linear structures: Arrays, linked lists, stacks, queues arrange elements sequentially. Arrays provide constant-time indexed access but linear-time insertion/deletion; linked lists offer constant-time insertion/deletion at known positions but linear-time access.
-
Hierarchical structures: Trees organize data with parent-child relationships. Binary search trees support efficient searching; heaps maintain priority order; tries handle string keys.
-
Graph structures: Vertices and edges represent relationships. Adjacency lists and matrices support graph algorithms.
-
Hash-based structures: Hash tables provide expected constant-time operations through key transformation and collision resolution.
-
Specialized structures: Bloom filters probabilistically test membership; segment trees answer range queries; union-find tracks disjoint sets.
Data Structure Design Considerations:
-
Operation set: What operations must be supported? Search, insert, delete, update, iterate? Different structures optimize different operation mixes.
-
Access patterns: Are operations random or sequential? Does locality matter? Does the structure support range queries?
-
Concurrency: Must multiple threads access the structure simultaneously? Lock-based, lock-free, and transactional designs address concurrency.
-
Persistence: Should previous versions remain accessible after modifications? Persistent structures enable time travel through data.
-
Memory constraints: Is memory abundant or scarce? Compact representations trade time for space.
Data Structure Selection Framework:
Choosing appropriate data structures involves matching requirements to capabilities:
- Characterize required operations and their frequencies
- Identify candidate structures with suitable operation complexities
- Consider practical factors: implementation complexity, memory overhead, cache behavior
- Prototype and benchmark if performance is critical
For example, implementing a symbol table in a compiler might require fast insertion and lookup by identifier name. A hash table provides expected O(1) operations; a balanced tree guarantees O(log n) but supports ordered traversal; a trie may be efficient for string keys with common prefixes. The choice depends on specific requirements and expected usage patterns.
This comprehensive reference organizes algorithmic knowledge into coherent parts, each building on previous foundations while maintaining flexibility for selective study.
Part I: Foundations establishes essential concepts and mathematical tools. Understanding these chapters provides the vocabulary and analytical framework for subsequent material.
Part II: Fundamental Data Structures covers structures that appear throughout algorithm design. Mastery of arrays, linked lists, trees, and hash tables enables efficient implementation of virtually any algorithm.
Part III: Sorting and Searching explores classic problems that illustrate algorithmic principles and provide building blocks for more complex algorithms.
Part IV: Advanced Data Structures extends fundamental structures to handle specialized requirements: string processing, range queries, dynamic connectivity.
Part V: Graph Algorithms addresses problems involving relationships and networks, from basic traversal to advanced flow algorithms.
Part VI: Algorithm Design Paradigms presents recurring patterns in algorithm design: divide and conquer, dynamic programming, greedy algorithms. Recognizing these patterns enables systematic approach to novel problems.
Part VII: Advanced Topics explores specialized areas reflecting current research and applications: randomized algorithms, approximation algorithms, computational geometry, parallel computing.
Part VIII: Practical Aspects bridges theory and practice, addressing implementation, testing, and real-world considerations.
The progression from foundations through advanced topics supports both sequential study and targeted reference. Each chapter includes theoretical exposition, algorithmic details, complexity analysis, and practical considerations, with exercises and references for deeper exploration.
Rigorous reasoning about algorithms requires facility with mathematical proof. Proof techniques establish correctness, bound complexity, and reveal structural properties. This section reviews essential proof methods with algorithmic applications.
A direct proof establishes a statement by logical deduction from known facts and definitions. The structure typically follows: assume premises, apply definitions, derive conclusion through valid inferences.
Example: Prove that the sum of two even integers is even.
Proof: Let a and b be even integers. By definition, there exist integers k and l such that a = 2k and b = 2l. Then a + b = 2k + 2l = 2(k + l). Since k + l is an integer, a + b is even. ∎
Direct proofs often proceed by expanding definitions and manipulating expressions algebraically. In algorithm analysis, direct proofs establish simple properties: "If an array is sorted, then binary search correctly determines membership" might be proved directly by induction on array length.
Proof by contradiction assumes the negation of the desired statement and derives a logical contradiction, establishing that the original statement must be true.
Example: Prove that √2 is irrational.
Proof: Assume, for contradiction, that √2 is rational. Then √2 = a/b where a and b are integers with no common factors (in lowest terms). Squaring both sides: 2 = a²/b², so a² = 2b². Thus a² is even, implying a is even. Write a = 2k. Substituting: (2k)² = 2b² → 4k² = 2b² → 2k² = b². Thus b² is even, so b is even. But then a and b share factor 2, contradicting that a/b was in lowest terms. Therefore our assumption must be false; √2 is irrational. ∎
In algorithms, proof by contradiction often establishes lower bounds or impossibility results. To show that comparison-based sorting requires Ω(n log n) comparisons, we assume a sorting algorithm uses fewer comparisons and derive contradiction with the number of possible permutations.
Mathematical induction proves statements about natural numbers. The principle: if a statement P(n) holds for a base case and whenever P(k) holds then P(k+1) holds, then P(n) holds for all n ≥ base.
Example: Prove that the sum of the first n natural numbers equals n(n+1)/2.
Base case (n = 1): 1 = 1(2)/2 = 1, true.
Inductive step: Assume the formula holds for n = k: 1 + 2 + ... + k = k(k+1)/2. Consider n = k+1: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2 Thus the formula holds for k+1.
By induction, the formula holds for all natural numbers n. ∎
Induction is indispensable for algorithm correctness proofs. Loop invariants are essentially inductive hypotheses: we prove the invariant holds initially (base case) and that if it holds before an iteration, it holds after (inductive step). When the loop terminates, the invariant yields the desired postcondition.
Strong Induction: Strong induction assumes P holds for all smaller values, not just the immediate predecessor, when proving P(k+1).
Example: Prove that every integer greater than 1 has a prime factorization.
Base case (n = 2): 2 is prime, so it has factorization (2).
Inductive step: Assume every integer from 2 up to k has a prime factorization. Consider k+1. If k+1 is prime, it has factorization (k+1). If composite, k+1 = ab where 2 ≤ a,b ≤ k. By the inductive hypothesis, a and b have prime factorizations; their product gives a factorization of k+1. ∎
Strong induction appears in algorithms where subproblems can be significantly smaller than the original, such as divide-and-conquer recurrences.
Structural induction generalizes mathematical induction to recursively-defined structures like trees or lists. To prove a property holds for all instances of a recursive structure, we show it holds for base cases and that if it holds for substructures, it holds for structures built from them.
Example: Prove that in any binary tree, the number of leaves exceeds the number of internal nodes by at most 1, with equality exactly for full binary trees.
Base case: A single node (leaf) has 1 leaf, 0 internal nodes; difference = 1.
Inductive step: Consider a tree T with root and left subtree L, right subtree R. Let leaves(T) = leaves(L) + leaves(R), internal(T) = 1 + internal(L) + internal(R). By induction, leaves(L) - internal(L) ≤ 1, similarly for R. Then: leaves(T) - internal(T) = (leaves(L)+leaves(R)) - (1+internal(L)+internal(R)) = (leaves(L)-internal(L)) + (leaves(R)-internal(R)) - 1 ≤ 1 + 1 - 1 = 1 Equality holds iff both subtrees have difference 1. ∎
Structural induction elegantly handles recursive algorithms that traverse tree structures.
Asymptotic analysis characterizes algorithm efficiency in terms of input size, abstracting away constant factors and lower-order terms. This abstraction reveals fundamental growth rates and enables comparison across algorithms and implementations.
Big-O notation provides an asymptotic upper bound. We say f(n) = O(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀, |f(n)| ≤ c·|g(n)|.
Intuitively, f grows no faster than g (up to constant factors). Common usage: "The algorithm runs in O(n²) time" means execution time is bounded above by some constant times n² for sufficiently large n.
Examples:
- 3n² + 5n + 2 = O(n²) because 3n² + 5n + 2 ≤ 4n² for n ≥ 5
- n log n = O(n²) because n log n ≤ n² for n ≥ 1 (though this bound is loose)
- 2ⁿ = O(3ⁿ) because 2ⁿ ≤ 1·3ⁿ for all n
Properties:
- Transitivity: If f = O(g) and g = O(h), then f = O(h)
- Sum: If f₁ = O(g₁) and f₂ = O(g₂), then f₁ + f₂ = O(max(g₁, g₂))
- Product: If f₁ = O(g₁) and f₂ = O(g₂), then f₁·f₂ = O(g₁·g₂)
Big-Omega provides an asymptotic lower bound. f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀, |f(n)| ≥ c·|g(n)|.
Intuitively, f grows at least as fast as g. Used to express best-case performance or inherent problem difficulty.
Examples:
- 3n² + 5n + 2 = Ω(n²) because 3n² + 5n + 2 ≥ 3n² for n ≥ 0
- n log n = Ω(n) because n log n ≥ n for n ≥ 2
Big-Theta gives tight asymptotic bounds. f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)). That is, f grows at the same rate as g (up to constants).
Examples:
- 3n² + 5n + 2 = Θ(n²)
- n log n + 2n = Θ(n log n)
- 2ⁿ + n¹⁰ = Θ(2ⁿ)
Little-o denotes strict upper bounds: f(n) = o(g(n)) if for every ε > 0, there exists n₀ such that for all n ≥ n₀, |f(n)| ≤ ε·|g(n)|. Intuitively, f grows strictly slower than g.
Examples:
- n = o(n log n)
- n log n = o(n²)
- n² = o(2ⁿ)
Little-ω denotes strict lower bounds: f(n) = ω(g(n)) if for every c > 0, there exists n₀ such that for all n ≥ n₀, |f(n)| ≥ c·|g(n)|. Equivalently, g(n) = o(f(n)).
Common Growth Rates (in increasing order):
- O(1): Constant
- O(log n): Logarithmic
- O(√n): Square root
- O(n): Linear
- O(n log n): Linearithmic
- O(n²): Quadratic
- O(n³): Cubic
- O(2ⁿ): Exponential
- O(n!): Factorial
Asymptotic Analysis in Practice: When analyzing algorithms, we typically:
- Count fundamental operations (comparisons, assignments, etc.)
- Express count as function of input size
- Simplify using asymptotic notation
- Compare with theoretical lower bounds
Recurrence relations express functions in terms of themselves, naturally arising from recursive algorithms. Solving recurrences reveals algorithm complexity.
The substitution method involves guessing the form of the solution and proving it correct by induction.
Example: Solve T(n) = 2T(n/2) + n, T(1) = 1.
Guess: T(n) = O(n log n), specifically T(n) ≤ c·n log n for some c.
Inductive hypothesis: Assume T(k) ≤ c·k log k for all k < n.
Inductive step: T(n) = 2T(n/2) + n ≤ 2·c·(n/2)·log(n/2) + n = c·n·(log n - 1) + n = c·n log n - c·n + n
We need T(n) ≤ c·n log n, so require -c·n + n ≤ 0 → c ≥ 1. Choose c = 1 and verify base case: T(1) = 1 ≤ 1·1·log 1 = 0? This fails because log 1 = 0. Base cases must be handled separately; we can choose c large enough to cover base cases.
The substitution method requires insight for guessing solutions but provides rigorous proofs once guesses are made.
Recursion trees visualize recurrence expansion, summing costs at each level.
Example: T(n) = 3T(n/4) + n²
Draw tree:
- Root: cost n², spawns 3 subproblems of size n/4
- Level 1: 3 nodes, each cost (n/4)² = n²/16, total cost 3n²/16
- Level 2: 9 nodes, each cost (n/16)² = n²/256, total cost 9n²/256
- Pattern continues until subproblems reach size 1
Number of levels: log₄ n (since problem size reduces by factor 4 each level)
Total cost = n² [1 + 3/16 + (3/16)² + ... + (3/16)^(log₄ n - 1)] + cost of base cases
Geometric series with ratio r = 3/16 < 1, so sum converges to constant. Thus T(n) = Θ(n²).
Recursion trees provide intuition and can be made rigorous through summation.
The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is asymptotically positive.
Theorem: Compare f(n) with n^(log_b a):
- If f(n) = O(n^(log_b a - ε)) for some ε > 0, then T(n) = Θ(n^(log_b a))
- If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) log n)
- If f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and a·f(n/b) ≤ c·f(n) for some c < 1 and sufficiently large n (regularity condition), then T(n) = Θ(f(n))
Examples:
- T(n) = 9T(n/3) + n: a=9, b=3, log_b a = 2, f(n)=n = O(n^(2-ε)) for ε=1 → Case 1: T(n)=Θ(n²)
- T(n) = T(2n/3) + 1: a=1, b=3/2, log_b a = 0, f(n)=1 = Θ(n^0) → Case 2: T(n)=Θ(log n)
- T(n) = 3T(n/4) + n log n: a=3, b=4, log_b a ≈ 0.792, f(n)=n log n = Ω(n^(0.792+ε)) with regularity? Check a·f(n/b) = 3·(n/4) log(n/4) ≤ (3/4)n log n for large n → Case 3: T(n)=Θ(n log n)
The Master Theorem covers many common recurrences but not all (e.g., when f(n) falls between cases or when recurrence has different form).
The Akra–Bazzi method generalizes the Master Theorem to recurrences of the form: T(n) = Σ a_i T(n/b_i) + f(n) where a_i > 0, b_i > 1, and f(n) satisfies certain conditions.
Method: Find p such that Σ a_i / b_i^p = 1. Then: T(n) = Θ( n^p (1 + ∫_1^n f(u)/u^(p+1) du) )
Example: T(n) = T(n/2) + T(n/3) + n
Find p: (1/2)^p + (1/3)^p = 1. By trial, p ≈ 0.787. Then: T(n) = Θ( n^0.787 (1 + ∫_1^n u/u^(1.787) du) ) = Θ( n^0.787 (1 + ∫_1^n u^(-0.787) du) ) = Θ( n^0.787 (1 + [u^(0.213)/0.213]_1^n) ) = Θ( n^0.787 (1 + (n^0.213 - 1)/0.213) ) = Θ(n)
The Akra–Bazzi method handles recurrences with unequal subproblem sizes and non-polynomial f(n).
Logarithms and exponentials pervade algorithm analysis. Understanding their properties is essential.
Definitions:
- log_b a = x means b^x = a
- Natural logarithm: ln a = log_e a, where e ≈ 2.71828
- Binary logarithm: lg a = log₂ a, common in computer science
Properties:
- log_b (xy) = log_b x + log_b y
- log_b (x/y) = log_b x - log_b y
- log_b (x^y) = y·log_b x
- log_b a = log_c a / log_c b (change of base)
- a^(log_b c) = c^(log_b a)
Exponential growth: Any exponential function (c^n with c > 1) eventually dominates any polynomial function (n^k). This underlies the distinction between polynomial-time and exponential-time algorithms.
Logarithmic growth: Logarithms grow slower than any positive power of n: log n = o(n^ε) for any ε > 0. This explains why logarithmic-time algorithms (binary search) are so efficient.
Iterated logarithm: log* n (log star) counts how many times we must apply logarithm to get below 1. For any practical n, log* n ≤ 5, appearing in advanced data structures like union-find with path compression.
Algorithm analysis frequently requires summing series.
Arithmetic series: Σ_{i=1}^n i = n(n+1)/2 = Θ(n²) Σ_{i=1}^n i² = n(n+1)(2n+1)/6 = Θ(n³) Σ_{i=1}^n i^k = Θ(n^(k+1)) for fixed k
Geometric series: Σ_{i=0}^n r^i = (r^(n+1) - 1)/(r - 1) for r ≠ 1 If |r| < 1, infinite sum converges: Σ_{i=0}^∞ r^i = 1/(1 - r)
Harmonic numbers: H_n = Σ_{i=1}^n 1/i = ln n + γ + 1/(2n) - ... where γ ≈ 0.57721 (Euler's constant) Thus H_n = Θ(log n)
Approximating sums:
- Integral method: ∫_m^n f(x) dx ≤ Σ_{i=m}^n f(i) ≤ ∫_{m-1}^{n-1} f(x) dx for decreasing f
- Bounding by geometric series when terms decrease exponentially
Combinatorial counting appears in algorithm analysis for counting possibilities, analyzing average cases, and bounding search spaces.
Permutations: Number of ways to order n distinct items: n! = n·(n-1)·...·1
Combinations: Number of ways to choose k items from n: C(n,k) = n!/(k!(n-k)!)
Properties:
- C(n,k) = C(n, n-k)
- Pascal's identity: C(n,k) = C(n-1,k-1) + C(n-1,k)
- Binomial theorem: (x + y)^n = Σ_{k=0}^n C(n,k) x^k y^(n-k)
Stirling's approximation: n! ~ √(2πn) (n/e)^n, useful for approximating factorials.
Pigeonhole principle: If n items are placed into m containers and n > m, then some container contains at least two items. Simple but powerful for lower bound proofs.
Randomized algorithms and average-case analysis require probability.
Basic concepts:
- Sample space: set of possible outcomes
- Event: subset of sample space
- Probability measure: function P satisfying 0 ≤ P(E) ≤ 1, P(Ω) = 1, and countable additivity
Conditional probability: P(A|B) = P(A ∩ B)/P(B), provided P(B) > 0
Independence: Events A and B are independent if P(A ∩ B) = P(A)·P(B)
Law of total probability: P(A) = Σ P(A|B_i)·P(B_i) for partition {B_i}
Bayes' theorem: P(B|A) = P(A|B)·P(B)/P(A)
Random variable: Function X: Ω → ℝ assigning numerical values to outcomes
Expectation: E[X] = Σ x·P(X = x) (discrete) or ∫ x·f(x) dx (continuous)
Linearity of expectation: E[aX + bY] = aE[X] + bE[Y] (holds even for dependent variables)
Variance: Var[X] = E[(X - E[X])²] = E[X²] - (E[X])²
Important distributions:
- Bernoulli: X = 1 with probability p, 0 with probability 1-p; E[X] = p, Var[X] = p(1-p)
- Binomial: Sum of n independent Bernoulli(p); E[X] = np, Var[X] = np(1-p)
- Geometric: Number of trials until first success; E[X] = 1/p
- Poisson: Approximation for rare events; P(X = k) = e^(-λ) λ^k/k!
Tail bounds:
- Markov: P(X ≥ a) ≤ E[X]/a for nonnegative X
- Chebyshev: P(|X - μ| ≥ kσ) ≤ 1/k²
- Chernoff: For sum of independent random variables, probability of deviation decays exponentially
Linear algebra appears in graph algorithms, machine learning, and scientific computing.
Vectors: Ordered lists of numbers; operations include addition, scalar multiplication, dot product
Matrices: Rectangular arrays; operations include addition, multiplication, transpose
Matrix multiplication: (AB){ij} = Σ_k A{ik} B_{kj}
Determinant: Scalar value characterizing matrix properties; det(AB) = det(A)·det(B)
Eigenvalues and eigenvectors: Av = λv; fundamental for PageRank, spectral clustering
Systems of linear equations: Ax = b; solved by Gaussian elimination, LU decomposition
Number theory underpins cryptography and some algorithm analysis.
Divisibility: a|b if there exists integer k such that b = a·k
Prime numbers: Integers >1 divisible only by 1 and themselves; infinitely many primes
Greatest common divisor: gcd(a,b) = largest d such that d|a and d|b; computed by Euclidean algorithm
Modular arithmetic: a ≡ b (mod m) if m|(a-b)
Chinese Remainder Theorem: System of congruences with coprime moduli has unique solution modulo product
Fermat's Little Theorem: If p is prime and a not divisible by p, then a^(p-1) ≡ 1 (mod p)
Euler's theorem: a^(φ(n)) ≡ 1 (mod n) for coprime a,n, where φ is Euler's totient function
RSA encryption: Relies on difficulty of factoring product of large primes
Time complexity quantifies the amount of time an algorithm requires as a function of input size. Unlike physical time measurements, complexity analysis counts fundamental operations, enabling machine-independent comparisons.
Operation Counting: The choice of which operations to count depends on the algorithm and analytical goals:
- Comparison-based algorithms count comparisons
- Arithmetic algorithms count arithmetic operations
- Graph algorithms may count edge traversals or vertex examinations
Example: Analyzing insertion sort
function insertionSort(A):
for i = 1 to length(A)-1:
key = A[i]
j = i-1
while j ≥ 0 and A[j] > key:
A[j+1] = A[j]
j = j-1
A[j+1] = key
Let n = length(A). The outer loop executes n-1 times. For each i, the inner while loop executes at most i times. Worst case (reverse sorted): total comparisons = Σ_{i=1}^{n-1} i = n(n-1)/2 = Θ(n²)
Instruction Counts: More detailed analysis might count all operations: assignments, comparisons, arithmetic. For insertion sort, worst-case assignments also Θ(n²). The constant factors differ but asymptotic growth remains.
Recurrence Analysis: Recursive algorithms lead to recurrences. Merge sort:
function mergeSort(A, left, right):
if left < right:
mid = (left + right)/2
mergeSort(A, left, mid)
mergeSort(A, mid+1, right)
merge(A, left, mid, right)
Merge operation on n elements takes Θ(n) time. Recurrence: T(n) = 2T(n/2) + Θ(n). By Master Theorem, T(n) = Θ(n log n).
Space complexity measures memory usage as function of input size. Includes:
- Input storage (sometimes excluded, focusing on additional memory)
- Auxiliary data structures
- Recursion stack space
In-place algorithms: Use O(1) additional space beyond input. Examples: insertion sort, heap sort (if implemented carefully).
Example: Merge sort requires Θ(n) auxiliary space for merging, plus O(log n) stack space for recursion. Total: Θ(n).
Space-time tradeoffs: Sometimes using more space reduces time. Dynamic programming often trades space (memoization) for time (avoiding recomputation).
Algorithms may perform differently on different inputs:
- Best case: Minimum time over all inputs of size n
- Worst case: Maximum time over all inputs
- Average case: Expected time over distribution of inputs
Example: Quicksort
- Best case: Pivot always splits evenly → O(n log n)
- Worst case: Pivot always smallest/largest → O(n²)
- Average case: Random pivots → O(n log n)
Significance: Worst-case guarantees are crucial for real-time systems; average-case matters for typical performance; best-case rarely informative alone.
Amortized analysis averages operation costs over a sequence, showing that while individual operations may be expensive, the average per operation is bounded.
Sum costs over sequence and divide by number of operations.
Example: Dynamic array with doubling
- Insert cost: 1 for normal insert, O(k) when array full (copying k elements)
- Sequence of n inserts: copies occur at sizes 1,2,4,8,..., up to n
- Total copies: 1+2+4+...+n/2 + n = 2n - 1 (if n is power of two)
- Plus n normal inserts: total cost ≤ 3n
- Amortized cost per insert: O(1)
Assign different charges to operations; credit built up by cheap operations pays for expensive ones.
Dynamic array example:
- Charge $3 per insert
- Actual cost $1 for normal insert, $k for resize
- When inserting into array of size m before resize:
- Pay $1 for actual insert
- Save $2: one for eventual copying of this element, one for copying of some older element
- When resize occurs, each of m elements has $1 saved for its copying
- Credit never negative; total charge ≤ 3n covers actual cost
Define potential function Φ mapping data structure state to real numbers. Amortized cost = actual cost + ΔΦ.
Dynamic array example: Φ = 2·size - capacity (for arrays with capacity ≥ size)
- Insert without resize: ΔΦ = 2 (size increases by 1, capacity unchanged) Amortized cost = 1 + 2 = 3
- Insert with resize: capacity doubles from m to 2m, size becomes m+1 ΔΦ = [2(m+1) - 2m] - [2m - m] = (2m+2-2m) - (m) = 2 - m Actual cost = m+1 Amortized cost = (m+1) + (2 - m) = 3
Potential method elegantly handles more complex sequences.
Lower bounds establish minimum resources required to solve a problem, independent of algorithm.
Comparison-based sorting: Any algorithm that sorts using only comparisons requires Ω(n log n) comparisons in worst case.
- Proof: n! possible permutations of input
- Each comparison yields binary outcome
- Decision tree with n! leaves requires height ≥ log₂(n!) = Ω(n log n)
Searching in sorted array: Binary search is optimal with Ω(log n) comparisons.
Decision trees model algorithms that make binary decisions based on comparisons. Each internal node represents a comparison; leaves represent outcomes.
Properties:
- Height = worst-case number of comparisons
- Leaves correspond to possible outputs
- For sorting, each permutation must appear as leaf
Applications:
- Proving lower bounds
- Analyzing average-case behavior
- Understanding information-theoretic limits
Information theory relates problem difficulty to number of possibilities. If there are N possible outputs, any algorithm must distinguish among them, requiring at least log₂ N bits of information.
Example: Finding maximum of n numbers
- n possibilities (which element is maximum)
- Lower bound: log₂ n comparisons? But we can find max in n-1 comparisons. Why the gap? Because comparisons yield more than one bit of information about ordering relationships.
Information-theoretic bounds provide starting points but may not be tight due to structural constraints.
Theoretical analysis complements empirical measurement:
- Profiling: Measure actual runtime, memory usage, cache misses
- Benchmarking: Compare algorithms on representative inputs
- Scalability testing: Verify asymptotic predictions on growing inputs
Challenges:
- Hardware dependencies: same algorithm may perform differently across systems
- Input sensitivity: performance depends on input characteristics
- Measurement noise: system load, caching effects
Modern memory hierarchies introduce cache complexity: number of cache misses as function of input size and cache parameters.
Ideal cache model: Computer with two-level memory hierarchy:
- Cache of size M, line size B
- Access to cache is free; access to main memory costs one miss
- Optimal offline cache replacement
Example: Matrix multiplication
- Standard triple loop: O(n³) operations but Θ(n³) cache misses with large matrices
- Blocked multiplication: process in blocks of size √M to fit in cache, reducing misses to Θ(n³/(B√M))
Cache-aware algorithms exploit known cache parameters; cache-oblivious algorithms perform well without parameter knowledge.
Parallel Random Access Machine (PRAM) models parallel computation with multiple processors accessing shared memory.
Variants:
- EREW (Exclusive Read, Exclusive Write)
- CREW (Concurrent Read, Exclusive Write)
- CRCW (Concurrent Read, Concurrent Write)
Complexity measures:
- Time: number of parallel steps
- Work: total operations across processors
- Speedup: sequential time / parallel time
- Efficiency: speedup / number of processors
Example: Parallel sum
- Divide array into pairs, sum in parallel
- Tree reduction: log n steps, n processors
- Work: O(n), time: O(log n)
Brent's theorem: If algorithm does W work in time T with P processors on EREW PRAM, then with P processors, time ≤ ⌈W/P⌉ + T
Parallel analysis reveals inherent parallelism and scalability limits.
Arrays represent the most fundamental data structure, providing contiguous memory allocation for sequences of elements. Understanding memory layout explains performance characteristics and limitations.
Contiguous allocation: Array elements stored in consecutive memory addresses. For an array of type T starting at address base, element i resides at address base + i·sizeof(T). This enables O(1) access through simple address arithmetic.
Memory alignment: Processors often require specific alignment for data types. Compilers insert padding between elements or at array boundaries to satisfy alignment constraints. For structures, padding ensures each field meets its alignment requirement.
Row-major vs column-major: Multi-dimensional arrays can be stored row-wise (C, C++) or column-wise (Fortran). Row-major stores entire first row consecutively, then second row; column-major stores first column, then second. Access pattern affects cache performance.
Static arrays: Fixed size determined at compile-time or allocation-time. Size cannot change after creation. Advantages: no overhead for size tracking, guaranteed contiguous memory. Disadvantages: cannot grow if more space needed.
Dynamic arrays: Abstract data type supporting resizing. Implementation typically uses:
- Pointer to heap-allocated memory
- Current size (number of elements)
- Current capacity (allocated space)
Operations:
- Access: O(1) via pointer arithmetic
- Append: amortized O(1) with resizing
- Insert/delete at position: O(n) due to shifting
When appending to full dynamic array:
Geometric growth: Multiply capacity by factor (typically 1.5 or 2)
- Amortized analysis shows O(1) per append
- Wasted space at most factor times size
- Copying cost amortized over insertions
Arithmetic growth: Add constant to capacity
- Append becomes O(n) amortized (since copies occur frequently)
- Example: add 100 each time: after n inserts, copies sum to Θ(n²)
Growth factor tradeoffs:
- Factor 2: simple, amortized analysis clean, but up to 100% waste
- Factor 1.5: less waste (33% maximum), but amortized bound still constant
- Golden ratio φ ≈ 1.618: historically used in some implementations
Contiguous 2D arrays:
int matrix[rows][cols]; // C-style
Access element (i,j) at base + i·cols·sizeof(T) + j·sizeof(T)
Array of arrays (jagged arrays):
int** matrix = malloc(rows * sizeof(int*));
for(i=0; i<rows; i++) matrix[i] = malloc(cols * sizeof(int));
Each row independently allocated; allows non-rectangular shapes but loses cache locality.
Performance implications:
- Contiguous 2D arrays: excellent spatial locality when accessing rows sequentially
- Array of arrays: potential TLB misses, multiple cache lines per row access
- Iteration order matters: row-major access in row-major storage maximizes cache hits
Arrays exploit spatial locality: accessing consecutive elements brings adjacent data into cache.
Cache lines: When accessing A[i], the entire cache line (typically 64 bytes) containing A[i] loads. Subsequent accesses to A[i+1] likely hit in cache.
Stride patterns:
- Sequential access (stride 1): optimal, uses full cache line
- Stride k: each access loads new cache line, wasting bandwidth
- Random access: potentially many cache misses
Example: Matrix multiplication
// Naive triple loop: poor locality for inner loops
for(i=0; i<n; i++)
for(j=0; j<n; j++)
for(k=0; k<n; k++)
C[i][j] += A[i][k] * B[k][j];
Access pattern: A row-wise (good), B column-wise (poor, large stride). Loop interchange improves:
for(i=0; i<n; i++)
for(k=0; k<n; k++)
for(j=0; j<n; j++)
C[i][j] += A[i][k] * B[k][j];
Now both A and B accessed row-wise.
When most elements are zero (or default), sparse representations save memory.
Compressed representations:
- Dictionary of keys: map (row,col) → value
- List of lists: each row stores list of (col,value) pairs
- Compressed sparse row (CSR): three arrays
- values: non-zero values in row-major order
- col_ind: column indices for each value
- row_ptr: starting index in values/col_ind for each row
CSR example:
Matrix:
[ 1 0 2 ]
[ 0 3 0 ]
[ 4 5 6 ]
values = [1,2,3,4,5,6]
col_ind = [0,2,1,0,1,2]
row_ptr = [0,2,3,6]
Row 0: values[0:2] at columns col_ind[0:2] → (0,1), (2,2) Row 1: values[2:3] → (1,3) at column 1 Row 2: values[3:6] at columns [0,1,2]
Operations:
- Matrix-vector multiply: O(nnz) time
- Sparse matrix addition: merge sorted lists
- Transpose: can be done in O(nnz) with careful algorithm
Singly linked lists consist of nodes, each containing data and a pointer to next node. Head pointer identifies first node; last node points to NULL.
Node structure:
struct Node {
int data;
Node* next;
};
Operations:
- Search: O(n) worst case, traverse until found
- Insert at beginning: O(1), update head
- Insert at end: O(n) without tail pointer, O(1) with tail
- Delete known node: O(1) if we have previous pointer, otherwise O(n) to find previous
- Delete by value: O(n) to find and O(1) to delete if found
Advantages: Dynamic size, O(1) insert/delete at known position Disadvantages: No random access, extra memory for pointers, poor cache locality
Each node has pointers to both next and previous nodes, enabling bidirectional traversal.
Node structure:
struct Node {
int data;
Node* prev;
Node* next;
};
Operations:
- All singly linked operations plus:
- Delete known node: O(1) without previous pointer
- Traverse backward: O(n) from tail
- Insert before known node: O(1) given node
Tradeoffs: Extra pointer per node (increased memory), but simpler deletion and backward traversal.
Last node points back to first (singly circular) or first's prev points to last (doubly circular).
Applications:
- Round-robin scheduling: cycle through processes
- Buffer management: reuse space circularly
- Multiplayer game turns
Operations:
- Traversal must detect cycle to avoid infinite loop
- Insert/delete similar to non-circular but handle wrap-around
Skip lists augment linked lists with multiple levels of express lanes, providing O(log n) expected search time.
Structure:
- Level 0: ordinary linked list with all elements
- Level i: linked list containing approximately every 2^i-th element (probabilistically)
- Each node randomly chooses its height (number of levels it participates in)
Search algorithm:
function search(skipList, target):
current = skipList.head
for level = maxLevel down to 0:
while current.forward[level] and
current.forward[level].data < target:
current = current.forward[level]
current = current.forward[0] // move to level 0
if current and current.data == target:
return current
return null
Insert: Choose random height, update pointers at each level where node appears.
Analysis:
- Expected search time: O(log n)
- Expected space: O(n) (each node contributes expected constant pointers)
- High probability bounds: search time O(log n) with high probability
Skip lists offer simpler implementation than balanced trees with comparable performance, used in databases (LevelDB) and in-memory indexes (Redis).
Linked lists involve per-node allocation, raising concerns:
Fragmentation: Many small allocations can fragment heap memory
- External fragmentation: free memory split into small unusable chunks
- Internal fragmentation: allocated blocks may be larger than needed due to alignment
Allocation overhead: Each malloc has metadata (size, next/prev pointers), typically 8-16 bytes per allocation. For small nodes, overhead can exceed data size.
Cache behavior: Nodes scattered in memory cause poor spatial locality; each traversal likely cache miss. Contrast with arrays where consecutive accesses hit cache.
Solutions:
- Node pooling: pre-allocate array of nodes, allocate from pool
- Compact linked lists: embed next pointers in arrays (like Linux kernel linked lists)
- Hybrid structures: unrolled linked lists store multiple elements per node
Stack follows Last-In-First-Out (LIFO) principle: push adds to top, pop removes from top.
Array-based stack:
class ArrayStack {
int* array;
int capacity;
int top; // index of top element, -1 for empty
void push(int x) {
if (top == capacity-1) resize();
array[++top] = x;
}
int pop() {
if (isEmpty()) error;
return array[top--];
}
}
All operations O(1) amortized; excellent cache locality.
Linked list stack:
class LinkedStack {
Node* head; // top of stack
void push(int x) {
Node* newNode = new Node(x);
newNode->next = head;
head = newNode;
}
int pop() {
if (isEmpty()) error;
int val = head->data;
Node* temp = head;
head = head->next;
delete temp;
return val;
}
}
All operations O(1); per-node allocation overhead.
Depth-First Search (DFS):
- Stack tracks vertices to explore
- Push starting vertex
- While stack not empty: pop vertex, process, push unvisited neighbors
- Natural recursion uses call stack implicitly
Expression parsing:
- Infix to postfix conversion (Shunting-yard algorithm)
- Evaluate postfix expressions: push operands, when operator pops operands, pushes result
- Check balanced parentheses: push opening, pop on closing, verify match
Function call management:
- Call stack stores return addresses, local variables
- Recursion depth limited by stack size
Undo operations:
- Push actions onto stack; pop to undo
Queue follows First-In-First-Out (FIFO): enqueue at rear, dequeue from front.
Array-based queue (circular buffer):
class ArrayQueue {
int* array;
int capacity;
int front, rear; // front index, rear index
int size;
void enqueue(int x) {
if (size == capacity) resize();
array[rear] = x;
rear = (rear + 1) % capacity;
size++;
}
int dequeue() {
if (isEmpty()) error;
int val = array[front];
front = (front + 1) % capacity;
size--;
return val;
}
}
All operations O(1); modulo arithmetic wraps around.
Linked list queue:
class LinkedQueue {
Node* head; // front
Node* tail; // rear
void enqueue(int x) {
Node* newNode = new Node(x);
if (tail) tail->next = newNode;
else head = newNode;
tail = newNode;
}
int dequeue() {
if (isEmpty()) error;
int val = head->data;
Node* temp = head;
head = head->next;
if (!head) tail = NULL;
delete temp;
return val;
}
}
All operations O(1) with tail pointer.
Circular queues reuse array space by wrapping indices modulo capacity. Essential for fixed-size buffers.
Full/empty distinction: Multiple approaches
- Maintain size counter
- Leave one slot empty: (rear+1)%capacity == front indicates full
- Use boolean flag
Applications:
- I/O buffers: producer-consumer
- Network packet queues
- Keyboard buffer
Double-ended queue supports insertion/deletion at both ends.
Implementation options:
- Doubly linked list: O(1) at both ends
- Circular array with head and tail indices: O(1) amortized at both ends
- Two stacks: amortized O(1) operations (one stack for front, one for back, transfer when empty)
Applications:
- Sliding window maximum
- Palindrome checking
- Undo-redo with ability to add/remove from both ends
Priority queue returns element with highest priority first. Usually implemented with heaps (Chapter 11).
Operations:
- insert: add element with priority
- extractMax: remove and return highest priority element
- increaseKey: modify priority of existing element
Applications:
- Dijkstra's algorithm
- Huffman coding
- Event-driven simulation
- Task scheduling
Hash functions map keys to array indices. Good hash functions:
- Deterministic: Same key always maps to same index
- Uniform: Distributes keys uniformly across array
- Efficient: Fast to compute
Division method: h(k) = k mod m
- Choose m prime not close to powers of 2 for better distribution
- Simple but may cluster if keys have patterns
Multiplication method: h(k) = ⌊m (kA mod 1)⌋ where 0 < A < 1
- Knuth suggests A ≈ (√5 - 1)/2 ≈ 0.618034 (golden ratio conjugate)
- Less sensitive to m choices
Universal hashing: Randomly choose hash function from family to minimize worst-case collisions
- Family H = {h_{ab}(k) = ((ak + b) mod p) mod m} for prime p > key range
- Probability of collision between distinct keys ≤ 1/m
String hashing:
- Polynomial rolling hash: h(s) = (s[0]·p^(n-1) + s[1]·p^(n-2) + ... + s[n-1]) mod m
- Common choices: p = 31 or 131, m large prime
- Java's String.hashCode(): s[0]·31^(n-1) + ... + s[n-1]
Each array slot points to linked list of colliding entries.
Operations:
- Insert: hash to slot, add to list (O(1) expected)
- Search: hash to slot, traverse list (O(1+α) expected, α = load factor)
- Delete: search then remove from list
Load factor α = n/m (number of entries / number of slots)
- Expected chain length = α
- Expected search time = O(1+α)
- Space overhead: pointers in chains
Advantages: Simple, handles high load factors gracefully Disadvantages: Poor cache locality, extra memory for pointers
All elements stored directly in array; collisions resolved by probing alternative slots.
Probe sequences: h(k,i) = (h'(k) + f(i)) mod m for i = 0,1,2,...
Linear probing: f(i) = i
- h(k,i) = (h'(k) + i) mod m
- Simple, good cache locality
- Primary clustering: long runs of occupied slots form, increasing search time
Quadratic probing: f(i) = i²
- h(k,i) = (h'(k) + c₁i + c₂i²) mod m
- Reduces clustering but may not probe all slots unless m prime and constants chosen carefully
Double hashing: f(i) = i·h₂(k)
- h(k,i) = (h₁(k) + i·h₂(k)) mod m
- h₂(k) must be nonzero and relatively prime to m
- Provides Θ(m²) distinct probe sequences, near-ideal
Operations:
- Insert: probe until empty slot found
- Search: probe until key found or empty slot encountered
- Delete: cannot simply mark empty (would break search for later keys). Use "deleted" marker.
Load factor limits: Performance degrades rapidly as α approaches 1. Typical resize when α > 0.7-0.8.
Universal families guarantee low collision probability regardless of input distribution.
Definition: Family H of hash functions from U to {0,...,m-1} is universal if for any distinct x,y ∈ U, number of h ∈ H with h(x)=h(y) ≤ |H|/m.
Implications: For random h from universal family, expected number of collisions with fixed x is at most (n-1)/m.
Construction: Choose prime p > maximum key. For a,b ∈ [0,p-1], define h_{ab}(x) = ((ax + b) mod p) mod m. This family is universal.
Perfect hashing: For static set of n keys, can construct two-level hash table with O(1) worst-case access and O(n) space.
- First level: universal hash to buckets
- Second level: for each bucket with n_i keys, use perfect hash of size Θ(n_i²) to guarantee no collisions
Perfect hashing provides O(1) worst-case access without collisions for static key sets.
Method (Fredman, Komlós, Szemerédi):
- Choose universal hash function h to map n keys to m = n buckets
- Let n_i be number of keys in bucket i
- For each bucket, allocate secondary table of size n_i² and find hash function with no collisions
- Expected total space: E[Σ n_i²] = O(n)
- Probability of failure in secondary table small; retry if needed
Cuckoo hashing (dynamic perfect hashing):
- Two hash tables T₁, T₂ with functions h₁, h₂
- Insert: try T₁; if occupied, evict to T₂; if T₂ occupied, evict back to T₁; continue
- May loop; after threshold, rehash with new functions
- Lookup: check both locations
- Expected O(1) operations, high probability bounds
Cuckoo hashing achieves O(1) worst-case lookup and amortized O(1) insertion using two hash tables.
Algorithm:
function insert(x):
if lookup(x): return
for count = 1 to MaxLoop:
if T₁[h₁(x)] empty:
T₁[h₁(x)] = x; return
swap(x, T₁[h₁(x)])
if T₂[h₂(x)] empty:
T₂[h₂(x)] = x; return
swap(x, T₂[h₂(x)])
rehash() // choose new functions, reinsert all
Properties:
- Lookup: check two locations O(1)
- Insert: expected O(1), amortized O(1) with high probability
- Space: load factor typically < 0.5 for good performance
- Deletion: simple removal
Variants:
- Multiple hash functions (d-ary cuckoo)
- Stash: small overflow area to reduce rehash probability
- Partial-key cuckoo: used in Facebook's memcached
Bloom filters are probabilistic data structures for membership queries with possible false positives but no false negatives.
Structure:
- Bit array of size m, initially all 0
- k independent hash functions h₁,...,h_k
Insert(x): Set bits at positions h₁(x),...,h_k(x) to 1
Query(x): Return true if all k bits are 1; false if any 0
False positive probability:
- After n inserts, probability specific bit still 0: (1 - 1/m)^(kn) ≈ e^(-kn/m)
- Probability all k bits 1 for non-member: (1 - e^(-kn/m))^k
Optimal k: k = (m/n) ln 2 minimizes false positives
Properties:
- Space efficient: ~10 bits per element for 1% false positive rate
- No deletions (standard version)
- Union and intersection possible with bitwise operations
Applications:
- Cache filtering: avoid disk lookups for non-existent items
- Database query optimization
- Blockchain (Bitcoin SPV nodes)
- Web caching (Akamai)
Consistent hashing minimizes remapping when hash table size changes, crucial for distributed systems.
Problem: In distributed hash tables, adding/removing nodes typically requires remapping most keys. Consistent hashing ensures only O(1/n) fraction remap.
Mechanism:
- Hash both keys and nodes to circular space [0,2³²-1]
- Each key assigned to first node clockwise from its position
- Node positions determined by hashing node identifier multiple times (virtual nodes)
Properties:
- When node added, only keys in arcs between new node and next node remap
- When node removed, its keys distribute to neighbors
- Virtual nodes balance load despite non-uniform node capacities
Applications:
- Distributed caching (Memcached)
- Distributed databases (Dynamo, Cassandra)
- Content delivery networks
Trees are hierarchical data structures consisting of nodes connected by edges.
Basic definitions:
- Root: Topmost node, no parent
- Parent: Node directly above in hierarchy
- Child: Node directly below
- Siblings: Nodes sharing same parent
- Leaf: Node with no children
- Internal node: Node with at least one child
- Subtree: Node and all its descendants
- Depth: Number of edges from root to node
- Height: Maximum depth of any node (sometimes defined as number of nodes on longest path)
- Level: Set of nodes at same depth
Tree properties:
- Connected: path exists between any two nodes
- Acyclic: no cycles
- n nodes have exactly n-1 edges
Each node has at most two children: left and right.
Binary tree types:
- Full: Every node has 0 or 2 children
- Complete: All levels filled except possibly last, which fills left to right
- Perfect: All internal nodes have 2 children, all leaves at same level
- Balanced: Height O(log n) (various definitions)
- Degenerate: Each node has at most one child (essentially linked list)
Properties:
- Maximum nodes at level i: 2^i
- Maximum nodes in tree of height h: 2^(h+1) - 1 (perfect tree)
- Minimum height for n nodes: ⌈log₂(n+1)⌉ - 1
Depth-First Traversals (recursive):
-
Preorder: Visit root, traverse left, traverse right
- Applications: copying tree, prefix expression
-
Inorder: Traverse left, visit root, traverse right
- For BST, yields sorted order
-
Postorder: Traverse left, traverse right, visit root
- Applications: deleting tree, postfix expression
Breadth-First Traversal (level order):
- Use queue: enqueue root, while queue not empty, dequeue node, enqueue children
- Visits nodes level by level
Morris traversal: Threaded binary tree traversal without stack or recursion, using temporary right pointers.
Binary trees represent arithmetic expressions: internal nodes are operators, leaves are operands.
Example: Expression (3 + 4) * (5 - 2)
*
/ \
+ -
/ \ / \
3 4 5 2
Traversals yield different notations:
- Preorder: * + 3 4 - 5 2 (prefix notation)
- Inorder: (3 + 4) * (5 - 2) (infix, needs parentheses)
- Postorder: 3 4 + 5 2 - * (postfix, RPN)
Evaluation: Postorder traversal computes value
Threaded binary trees add pointers to inorder predecessor/successor, enabling traversal without stack/recursion.
Types:
- Single-threaded: each node has thread to inorder successor
- Double-threaded: threads to both predecessor and successor
Node structure:
struct ThreadedNode {
int data;
ThreadedNode* left;
ThreadedNode* right;
bool leftThread; // true if left is thread
bool rightThread; // true if right is thread
};
Traversal:
function inorder(root):
current = leftmost(root)
while current:
visit(current)
if current.rightThread:
current = current.right
else:
current = leftmost(current.right)
Trees where nodes can have arbitrary number of children.
Representations:
- First child/next sibling: Each node has pointer to first child and next sibling (transforms to binary tree)
- Array of child pointers: Each node stores list/array of children
- Linked lists: Children stored in linked list
Conversion to binary tree: Left child = first child, right child = next sibling. This binary representation preserves tree structure.
Binary Search Tree property: For every node, all keys in left subtree < node key < all keys in right subtree.
Variations:
- Duplicate keys: typically store in left or right consistently, or augment node with count
- Ordering: can be non-strict (≤) depending on definition
Operations all maintain BST property.
Search:
function search(root, key):
if not root or root.key == key:
return root
if key < root.key:
return search(root.left, key)
else:
return search(root.right, key)
Time: O(h) where h is height
Insert:
function insert(root, key):
if not root:
return newNode(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
Time: O(h)
Delete: Three cases
- Leaf: simply remove
- One child: replace with child
- Two children: find inorder successor (minimum in right subtree), copy its value, delete successor
function delete(root, key):
if not root: return null
if key < root.key:
root.left = delete(root.left, key)
else if key > root.key:
root.right = delete(root.right, key)
else:
// case 1 & 2
if not root.left: return root.right
if not root.right: return root.left
// case 3
minNode = findMin(root.right)
root.key = minNode.key
root.right = delete(root.right, minNode.key)
return root
Time: O(h)
Worst case: Degenerate tree (insert sorted order) → height = n → operations O(n)
Average case: Random insert order yields expected height O(log n)
- Random BST height ~ 4.3 ln n (approximately)
Best case: Perfectly balanced → height ⌊log₂ n⌋ → operations O(log n)
Store additional information in nodes to support queries beyond basic BST.
Example: Order-statistic tree (size of subtree)
- Each node stores size = size(left) + size(right) + 1
- Find k-th smallest: compare k with left size
Example: Interval tree (max endpoint in subtree)
- Store intervals [low,high]
- Each node stores max endpoint in its subtree
- Find overlapping interval
Example: Range count queries (sum of values in key range)
- Store sum of values in subtree
- Query [L,R] by traversing both sides
Augmentation must be maintainable during insert/delete in O(log n).
Balanced trees maintain height O(log n) through restructuring operations after insert/delete.
AVL trees maintain balance factor = height(left) - height(right) ∈ {-1,0,1}. After insert/delete, if balance factor becomes ±2, restructure via rotations.
Rotations:
- Left rotation: When right subtree too heavy
- Right rotation: When left subtree too heavy
- Left-Right rotation: Left child right-heavy → left rotate child, then right rotate node
- Right-Left rotation: Right child left-heavy → right rotate child, then left rotate node
Insertion:
- Standard BST insert
- Update heights on path to root
- If imbalance detected, perform appropriate rotation
Deletion:
- Standard BST delete
- Update heights and rebalance up to root (may require multiple rotations)
Properties:
- Height ≤ 1.44 log₂ n (worst case)
- Search O(log n), insert/delete O(log n)
- More rigid balance than red-black, potentially more rotations
Red-black trees maintain approximate balance through node colors and constraints:
Properties:
- Every node red or black
- Root black
- All leaves (NULL) black
- Red node cannot have red parent (no two consecutive reds)
- Every path from root to leaf has same number of black nodes (black-height)
Consequences: Longest path ≤ 2 × shortest path → height ≤ 2 log₂(n+1)
Insertion: Standard BST insert (new node red), then fix violations:
- Case 1: Uncle red → recolor parent, grandparent, uncle; move up
- Case 2: Uncle black, node inside → rotate to make outside
- Case 3: Uncle black, node outside → rotate grandparent, recolor
Deletion: More complex; involves "double black" concept and rotations/color changes
Properties:
- O(log n) operations
- Fewer rotations than AVL on average
- Used in C++ STL map, Java TreeMap, Linux kernel
Splay trees are self-adjusting: accessed nodes move to root via splaying operations. No explicit balance condition.
Splay operations:
- Zig: Single rotation when node is child of root
- Zig-zig: Two rotations in same direction
- Zig-zag: Two rotations in opposite directions
Operations:
- Search: splay accessed node to root
- Insert: splay new node to root
- Delete: splay node to root, remove, splay max of left subtree
Amortized analysis: Any sequence of m operations on n-node tree takes O(m log n) time (using potential function based on log of subtree sizes)
Properties:
- Simple, no balance information stored
- Recently accessed nodes near root (good for locality)
- Amortized O(log n) per operation
- Used in cache implementations, garbage collectors
Treaps combine BST property with heap property: each node has (key, priority). Tree is BST by key, heap (max) by priority.
Operations:
- Insert: BST insert by key, then rotate up until heap property satisfied
- Delete: rotate down until leaf, then remove
- Search: standard BST search
Random priorities yield balanced tree with high probability:
- Expected depth O(log n)
- Simple implementation
Properties:
- Randomized, no complex balancing logic
- Expected O(log n) operations
- Used in randomized algorithm contexts
B-trees are balanced search trees optimized for disk storage (large block sizes). Each node can have many children.
Properties (order m):
- Root: 1 to m-1 keys (2 to m children)
- Internal nodes: ⌈m/2⌉-1 to m-1 keys (⌈m/2⌉ to m children)
- Leaves: ⌈m/2⌉-1 to m-1 keys
- All leaves at same depth
Operations:
- Search: traverse from root, following appropriate child pointers
- Insert: find leaf, insert key. If leaf full, split into two leaves, promote middle key to parent. May propagate splits upward.
- Delete: remove key, possibly merge or redistribute with siblings
Height: For n keys and order m, height ≤ log_{⌈m/2⌉} n
Applications: Database indexing, file systems
B+ trees variant where all keys appear in leaves, internal nodes store only routing information.
Properties:
- Internal nodes: keys for guiding search (no data)
- Leaves: linked list for efficient range queries
- Data pointers only in leaves
Advantages:
- Range queries efficient via leaf links
- Higher fanout (internal nodes store only keys)
- Consistent search performance
Applications: Most database indexes (MySQL InnoDB), filesystems
2-3 trees are B-trees of order 3:
- 2-nodes: one key, two children
- 3-nodes: two keys, three children
- All leaves at same level
Operations:
- Search: traverse appropriate child
- Insert: find leaf, insert. If leaf becomes 3-node with overflow, split and promote
- Delete: complex, involves merging and redistribution
Properties:
- Height ≤ log₂ n
- Simple conceptually, but 2-3-4 trees (red-black equivalent) easier to implement
AA trees are variant of red-black trees with simplified rules: only right children can be red, no left reds. Each node stores level (analogous to black-height).
Properties:
- Level of leaf = 1
- Red node has same level as parent
- Black node has level one less than parent
Operations:
- Skew: eliminate left reds (right rotation)
- Split: eliminate consecutive right reds (left rotation, increase level)
Advantages: Simpler implementation than red-black, fewer cases
Binary heap is complete binary tree satisfying heap property:
- Max-heap: parent ≥ children
- Min-heap: parent ≤ children
Array representation:
- Root at index 1 (or 0)
- For node i: left child 2i, right child 2i+1, parent ⌊i/2⌋
- Complete tree ensures compact storage
Operations:
- insert: Add at end, bubble up until heap property restored O(log n)
- extractMax: Replace root with last element, bubble down O(log n)
- buildHeap: Bottom-up bubbling O(n) (not O(n log n))
Heapify (bubble down):
function heapify(array, n, i):
largest = i
left = 2i
right = 2i+1
if left ≤ n and array[left] > array[largest]:
largest = left
if right ≤ n and array[right] > array[largest]:
largest = right
if largest != i:
swap(array[i], array[largest])
heapify(array, n, largest)
Applications: Priority queues, heap sort
Generalization where each node has d children. Array representation: children of i are d·i - (d-2) to d·i + 1.
Properties:
- Height: log_d n
- insert: O(log_d n)
- extractMax: O(d log_d n) (bubble down compares d children)
Tradeoffs:
- Larger d reduces height but increases per-level work
- Better cache behavior (fewer levels)
- Used in Dijkstra's algorithm implementations
Fibonacci heaps support decrease-key efficiently, crucial for Dijkstra and Prim algorithms.
Structure:
- Collection of heap-ordered trees
- Roots in circular doubly linked list
- Each node has degree, child list, mark bit (for history)
- Lazy consolidation: trees merged only during extractMin
Operations:
- insert: add to root list O(1)
- merge: concatenate root lists O(1)
- extractMin: remove minimum, promote children to root list, consolidate trees of same degree O(log n) amortized
- decreaseKey: cut node from parent, add to root list, possibly cascade cuts O(1) amortized
- delete: decreaseKey to -∞, extractMin
Amortized analysis uses potential function = trees + 2·marked nodes
Properties:
- extractMin O(log n) amortized, others O(1) amortized
- Complex implementation
- Mostly theoretical interest; pairing heaps often used in practice
Binomial heap is collection of binomial trees satisfying heap property.
Binomial tree B_k:
- Root has degree k
- Children are B₀, B₁, ..., B_{k-1}
- Size = 2^k
Structure:
- Forest of binomial trees, each heap-ordered
- At most one tree of each degree (like binary representation)
Operations:
- merge: combine forests like binary addition O(log n)
- insert: merge with singleton heap O(log n)
- extractMin: find minimum root, remove, merge children with heap O(log n)
- decreaseKey: bubble up O(log n)
Properties:
- All operations O(log n) worst-case
- More predictable than Fibonacci heap
- Used in some priority queue implementations
Pairing heaps are self-adjusting heaps with simpler structure than Fibonacci but similar amortized bounds.
Structure: Each node has left child and next sibling (like binary tree representation of general tree)
Operations:
- insert: add as new root, merge by linking
- merge: link two heaps (larger root becomes child of smaller)
- extractMin: remove root, merge pairs of subtrees (two-pass merging)
Analysis: Amortized O(log n) for extractMin, O(1) for others (conjectured, proven for some variants)
Properties:
- Simple implementation
- Good practical performance
- Used in GNU libstdc++ priority_queue
Soft heap trades accuracy for speed: allows "corruptions" (increasing keys) to achieve O(1) amortized time for all operations.
Structure: Binomial heap variant with error parameter ε
Properties:
- findMin returns approximate minimum (may be corrupted)
- insert, merge, deleteMin all O(1) amortized
- At most ε·n corrupted items
Applications: Used in deterministic selection algorithms (median of medians can be simplified)
Repeatedly swap adjacent elements if out of order; largest element "bubbles" to end.
function bubbleSort(array):
n = array.length
for i = 0 to n-1:
swapped = false
for j = 0 to n-i-2:
if array[j] > array[j+1]:
swap(array[j], array[j+1])
swapped = true
if not swapped: break
Complexity:
- Worst/average: O(n²) comparisons and swaps
- Best: O(n) (already sorted, early exit)
- Space: O(1) in-place
Properties:
- Stable (equal elements maintain relative order)
- Adaptive (early termination)
- Poor performance, mainly educational
Repeatedly find minimum element and place at beginning.
function selectionSort(array):
n = array.length
for i = 0 to n-1:
minIndex = i
for j = i+1 to n-1:
if array[j] < array[minIndex]:
minIndex = j
swap(array[i], array[minIndex])
Complexity:
- Always O(n²) comparisons (n(n-1)/2)
- O(n) swaps (good when swap expensive)
- Space: O(1)
Properties:
- Not stable (but can be made stable with careful implementation)
- Not adaptive
- Minimal data movement
Build sorted sequence by inserting each element into correct position.
function insertionSort(array):
n = array.length
for i = 1 to n-1:
key = array[i]
j = i-1
while j ≥ 0 and array[j] > key:
array[j+1] = array[j]
j--
array[j+1] = key
Complexity:
- Worst: O(n²) (reverse sorted)
- Average: O(n²)
- Best: O(n) (already sorted)
- Space: O(1)
Properties:
- Stable
- Adaptive (excellent for nearly sorted data)
- Online (can sort as elements arrive)
- Excellent for small arrays (used as base case in hybrid sorts)
Stability: Stable sorts preserve relative order of equal elements. Important when sorting by multiple keys.
Adaptiveness: Adaptive sorts perform better on partially sorted data. Measured by number of inversions (pairs out of order). Insertion sort O(n + inversions).
Divide-and-conquer: split array, recursively sort halves, merge.
function mergeSort(array, left, right):
if left < right:
mid = (left + right) // 2
mergeSort(array, left, mid)
mergeSort(array, mid+1, right)
merge(array, left, mid, right)
function merge(array, left, mid, right):
// merge sorted subarrays [left..mid] and [mid+1..right]
temp = new array[right-left+1]
i = left, j = mid+1, k = 0
while i ≤ mid and j ≤ right:
if array[i] ≤ array[j]:
temp[k++] = array[i++]
else:
temp[k++] = array[j++]
while i ≤ mid: temp[k++] = array[i++]
while j ≤ right: temp[k++] = array[j++]
copy temp back to array[left..right]
Complexity:
- Time: Θ(n log n) always
- Space: Θ(n) auxiliary (can be O(1) with linked lists)
- Stable
Optimizations:
- Use insertion sort for small subarrays
- Avoid copying by alternating arrays
- Natural merge sort exploits existing runs
Divide-and-conquer: partition around pivot, recursively sort partitions.
function quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi-1)
quickSort(array, pi+1, high)
function partition(array, low, high):
pivot = array[high] // Lomuto scheme
i = low - 1
for j = low to high-1:
if array[j] ≤ pivot:
i++
swap(array[i], array[j])
swap(array[i+1], array[high])
return i+1
Alternative: Hoare partition (more efficient, more swaps)
Complexity:
- Average: Θ(n log n)
- Worst: Θ(n²) (bad pivot choices)
- Space: O(log n) stack space (in-place partitioning)
Pivot selection:
- Random: avoids worst-case with high probability
- Median-of-three: first, middle, last
- Introspective: switch to heapsort if recursion depth excessive
Optimizations:
- Use insertion sort for small subarrays
- Three-way partitioning for duplicates (Dutch national flag)
Build max heap, repeatedly extract maximum.
function heapSort(array):
// Build heap (rearrange array)
n = array.length
for i = n/2-1 down to 0:
heapify(array, n, i)
// Extract elements from heap
for i = n-1 down to 0:
swap(array[0], array[i])
heapify(array, i, 0)
Complexity:
- Time: Θ(n log n) always
- Space: O(1) in-place
- Not stable
Properties:
- No worst-case quadratic (unlike quicksort)
- Poor cache performance (access pattern jumps)
- Used in hybrid sorts as fallback
Hybrid sorting algorithm combining quicksort, heapsort, insertion sort:
- Begin with quicksort
- If recursion depth exceeds 2 log n, switch to heapsort
- Use insertion sort for small subarrays (< 16 elements)
Properties:
- O(n log n) worst-case
- Fast average case (quicksort)
- Used in C++ std::sort, .NET Array.Sort
Hybrid stable sorting algorithm derived from merge sort and insertion sort:
- Scan array to identify natural runs (increasing or decreasing)
- Push runs onto stack
- Merge runs when top runs meet criteria (like maintaining balance)
- Use insertion sort for small runs
Properties:
- O(n log n) worst-case
- O(n) on partially sorted data
- Stable
- Used in Python, Java, Android
Sort integers in range [0,k] by counting occurrences.
function countingSort(array, k):
count = array of size k+1 initialized to 0
output = array of size n
// Count occurrences
for i = 0 to n-1:
count[array[i]]++
// Cumulative count (positions)
for i = 1 to k:
count[i] += count[i-1]
// Build output (stable)
for i = n-1 down to 0:
output[count[array[i]]-1] = array[i]
count[array[i]]--
return output
Complexity:
- Time: Θ(n + k)
- Space: Θ(n + k)
- Stable
Constraints: Integer keys, k not too large
Sort by processing digits individually, from least significant to most significant.
function radixSort(array, d):
for i = 0 to d-1:
use stable sort (counting sort) on digit i
Complexity:
- Time: Θ(d·(n + k)) where k is digit range (usually 10 or 256)
- Space: Θ(n + k)
Variants:
- LSD (least significant digit): must use stable sort
- MSD (most significant digit): recursive, can sort in place
Applications: Sorting integers, strings (if fixed length)
Distribute elements into buckets, sort each bucket individually.
function bucketSort(array):
n = array.length
buckets = array of n empty lists
// Distribute into buckets
for i = 0 to n-1:
bucketIndex = floor(n * array[i])
buckets[bucketIndex].append(array[i])
// Sort each bucket
for i = 0 to n-1:
insertionSort(buckets[i])
// Concatenate buckets
result = []
for i = 0 to n-1:
result.extend(buckets[i])
Complexity:
- Average: Θ(n) if distribution uniform
- Worst: Θ(n²) (all in one bucket)
- Space: Θ(n)
Applications: Floating point numbers, uniform distributions
QuickSelect: partition array around random pivot, recurse on side containing k-th smallest.
function quickSelect(array, left, right, k):
if left == right:
return array[left]
pivotIndex = random(left, right)
pivotIndex = partition(array, left, right, pivotIndex)
if k == pivotIndex:
return array[k]
else if k < pivotIndex:
return quickSelect(array, left, pivotIndex-1, k)
else:
return quickSelect(array, pivotIndex+1, right, k)
Complexity:
- Expected: O(n)
- Worst: O(n²) (unlucky pivots)
Deterministic selection with guaranteed O(n) worst-case.
Algorithm:
- Divide array into groups of 5
- Find median of each group (sort each group of 5)
- Recursively find median of medians (pivot)
- Partition around pivot
- Recurse on appropriate side
Analysis:
- At least 3n/10 elements ≤ pivot (and ≥ pivot) due to median property
- Recurrence: T(n) ≤ T(n/5) + T(7n/10) + O(n)
- Solves to T(n) = O(n)
Complex in practice due to constant factors; mainly theoretical importance
Selection algorithms find k-th smallest element. Applications:
- Median (k = n/2)
- Percentiles
- Finding "typical" value
Sequentially scan array until target found.
function linearSearch(array, target):
for i = 0 to array.length-1:
if array[i] == target:
return i
return -1
Complexity:
- Worst: O(n)
- Average: O(n) (if target present with equal probability)
- Best: O(1)
Properties: Works on unsorted data, simple
Search sorted array by repeatedly dividing interval in half.
function binarySearch(array, target):
left = 0, right = array.length-1
while left ≤ right:
mid = left + (right - left) // 2
if array[mid] == target:
return mid
else if array[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Complexity:
- Time: O(log n)
- Space: O(1) iterative, O(log n) recursive
Variants:
- Lower bound: first position ≥ target
- Upper bound: first position > target
- Search in rotated array
Improves on binary search for uniformly distributed data by estimating position.
function interpolationSearch(array, target):
left = 0, right = array.length-1
while left ≤ right and target ≥ array[left] and target ≤ array[right]:
if left == right:
return left if array[left] == target else -1
// Estimate position
pos = left + ((target - array[left]) * (right - left))
// (array[right] - array[left])
if array[pos] == target:
return pos
if array[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
Complexity:
- Average: O(log log n) for uniform distribution
- Worst: O(n) (non-uniform)
Find range containing target by doubling step, then binary search.
function exponentialSearch(array, target):
if array[0] == target: return 0
bound = 1
while bound < array.length and array[bound] ≤ target:
bound *= 2
return binarySearch(array, target, bound/2, min(bound, array.length-1))
Complexity: O(log i) where i is target position Applications: Unbounded/infinite arrays
Divide into three parts (not generally better than binary). Useful for unimodal functions.
function ternarySearch(f, left, right, eps):
while right - left > eps:
m1 = left + (right - left) / 3
m2 = right - (right - left) / 3
if f(m1) < f(m2):
left = m1
else:
right = m2
return (left + right) / 2
Applications: Finding maximum of unimodal function
Tree structure for storing strings where each node represents a common prefix.
Structure:
- Root represents empty string
- Each node has array of children (one per possible character)
- Nodes may mark end of word
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
Operations:
- Insert: traverse/create nodes for each character, mark end
- Search: traverse characters, check end at final node
- StartsWith: traverse characters, return true if path exists
Complexity:
- Time: O(L) per operation (L = string length)
- Space: O(alphabet_size · total_characters) worst case
Optimizations:
- Compressed trie: merge nodes with single child
- Ternary search trie: each node has three children (less, equal, greater)
Merge chains of single-child nodes into single edges with labels.
Example: Strings "bear", "bell", "bid", "bull" → common prefixes "be", "b" shared
Advantages: Reduced space, faster traversal Disadvantages: More complex implementation
Compact trie of all suffixes of a string. Each leaf corresponds to suffix; internal nodes represent repeated substrings.
Construction:
- Ukkonen's algorithm: O(n) time, online
- McCreight's algorithm: simpler, O(n) time
Applications:
- Pattern matching: O(m) time after O(n) preprocessing
- Longest repeated substring
- Longest common substring (multiple strings via generalized suffix tree)
- Palindrome detection
Sorted array of all suffixes of a string. Each entry is starting index of suffix.
Example: "banana" suffixes: "banana", "anana", "nana", "ana", "na", "a" Sorted: "a", "ana", "anana", "banana", "na", "nana" Suffix array: [5,3,1,0,4,2]
Construction:
- Naive: O(n² log n)
- Manber-Myers: O(n log n)
- SA-IS: O(n) (complex)
LCP Array: Longest Common Prefix between consecutive suffixes in suffix array
- Kasai's algorithm: O(n) from suffix array
Applications: Pattern matching (binary search on suffix array + LCP)
Builds finite state machine for multiple pattern matching. Automaton has failure links for efficient backtracking.
Construction:
- Build trie of patterns
- Add failure links (like KMP failure function generalized to multiple patterns)
- Add output links to propagate matches
Search: O(n + m + z) where n = text length, m = total pattern length, z = matches
Applications: Virus scanning, intrusion detection, multi-pattern search
Segment trees answer range queries (sum, min, max) and support point updates in O(log n).
Structure: Binary tree where each node represents segment [l,r]
- Leaf: single element
- Internal node: combines children's values
Operations:
- Build: O(n)
- Query: traverse relevant segments O(log n)
- Update: update leaf and propagate O(log n)
class SegmentTree {
int[] tree;
int n;
SegmentTree(int[] arr) {
n = arr.length;
tree = new int[4*n];
build(arr, 1, 0, n-1);
}
void build(int[] arr, int node, int l, int r) {
if (l == r) {
tree[node] = arr[l];
} else {
int mid = (l + r)/2;
build(arr, 2*node, l, mid);
build(arr, 2*node+1, mid+1, r);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
int query(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql ≤ l && r ≤ qr) return tree[node];
int mid = (l + r)/2;
return query(2*node, l, mid, ql, qr) +
query(2*node+1, mid+1, r, ql, qr);
}
}
Extends segment tree to support range updates (add constant to range) efficiently.
Idea: Store pending updates at nodes; propagate only when needed during queries.
void updateRange(int node, int l, int r, int ul, int ur, int val) {
if (lazy[node] != 0) {
tree[node] += (r-l+1) * lazy[node];
if (l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (ul > r || ur < l) return;
if (ul ≤ l && r ≤ ur) {
tree[node] += (r-l+1) * val;
if (l != r) {
lazy[2*node] += val;
lazy[2*node+1] += val;
}
return;
}
int mid = (l + r)/2;
updateRange(2*node, l, mid, ul, ur, val);
updateRange(2*node+1, mid+1, r, ul, ur, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
Extend to 2D arrays: tree of trees where each node contains segment tree for that row range.
Operations: O(log² n) for queries/updates Space: O(n²) (can be optimized with fractional cascading)
Simpler structure for prefix sums and point updates.
Idea: Each index i stores sum of range (i - lsb(i) + 1) to i, where lsb is least significant set bit.
Operations:
class FenwickTree {
int[] bit;
int n;
FenwickTree(int n) {
this.n = n;
bit = new int[n+1];
}
void update(int idx, int delta) {
while (idx ≤ n) {
bit[idx] += delta;
idx += idx & -idx; // add lsb
}
}
int query(int idx) { // prefix sum [1..idx]
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & -idx;
}
return sum;
}
}
Complexity: O(log n) per operation Space: O(n) Applications: Inversion count, frequency counting, range sum queries
Union-Find maintains partition of elements into disjoint sets. Supports:
- find(x): find representative of set containing x
- union(x,y): merge sets containing x and y
Basic array implementation:
class UnionFind {
int[] parent;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x)
x = parent[x];
return x;
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY)
parent[rootY] = rootX;
}
}
Time: O(n) worst case for find (chain)
Optimize find by making nodes point directly to root.
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
Attach smaller tree to larger tree's root to keep height small.
class UnionFind {
int[] parent;
int[] rank; // or size
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
With both optimizations:
- find: O(α(n)) amortized, where α is inverse Ackermann function (≤ 5 for practical n)
- union: O(α(n))
- Almost constant time in practice
Applications:
- Kruskal's MST algorithm
- Connected components in graphs
- Image segmentation
- Percolation theory
All versions accessible but only latest modifiable. Implement via fat nodes or path copying.
Fat nodes: Each node stores multiple versions with timestamps. When modifying, add new version to node. May need to follow pointers to correct version.
Path copying: Copy nodes along path to root when modifying. Share unchanged subtrees.
Example: Persistent binary search tree
- Insert: copy nodes from root to new leaf
- Old root still points to old tree
All versions modifiable. Requires version graph and merge operations.
Implementation:
- Each node stores modifications with version stamps
- Find correct version by walking version DAG
Immutable data structures where operations return new structure without modifying old. Inherently persistent.
Examples:
- Functional lists (cons cells)
- Okasaki's book on purely functional data structures
- Red-black trees with path copying
Advantages: Thread safety, undo/redo, reasoning Disadvantages: Space overhead, garbage collection
Adjacency list represents a graph as an array of lists, where list[i] contains all vertices adjacent to vertex i.
Structure:
class Graph {
int V; // number of vertices
List<Integer>[] adj; // adjacency lists
Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++)
adj[i] = new ArrayList<>();
}
void addEdge(int u, int v) {
adj[u].add(v); // for directed graph
adj[v].add(u); // add this line for undirected
}
}
Space Complexity:
- Directed graph: O(V + E)
- Undirected graph: O(V + 2E) = O(V + E)
Time Complexity:
- Check if u and v adjacent: O(degree(u)) worst case
- Iterate over neighbors of u: O(degree(u))
- Add edge: O(1)
Variants:
- Weighted graphs: Store pairs (neighbor, weight)
- Multigraphs: Allow duplicate edges
- Compressed adjacency lists: Use arrays for better cache locality
Adjacency matrix is a V × V matrix where matrix[u][v] = 1 if edge exists, 0 otherwise.
Structure:
class Graph {
int V;
boolean[][] adj;
Graph(int V) {
this.V = V;
adj = new boolean[V][V];
}
void addEdge(int u, int v) {
adj[u][v] = true;
adj[v][u] = true; // for undirected
}
}
Space Complexity: Θ(V²) regardless of edges Time Complexity:
- Check adjacency: O(1)
- Iterate neighbors: O(V)
- Add edge: O(1)
Advantages:
- Constant-time edge existence check
- Simple implementation
- Good for dense graphs
Disadvantages:
- Large memory footprint for sparse graphs
- Iterating over neighbors is O(V) even for low-degree vertices
Optimizations:
- Bit matrices: Use bitsets for boolean matrices
- Compressed sparse row: For weighted graphs with many zeros
Incidence matrix is V × E matrix where matrix[v][e] = 1 if vertex v incident to edge e.
Structure:
class Graph {
int V, E;
int[][] inc; // incidence matrix
Graph(int V, int E) {
this.V = V;
this.E = E;
inc = new int[V][E];
}
}
For directed graphs: matrix[v][e] = -1 if edge leaves v, 1 if enters v, 0 otherwise.
Space Complexity: Θ(V·E) - rarely used due to size Applications: Network flow algorithms, theoretical graph theory
Simple list of all edges.
Structure:
class Edge {
int u, v;
int weight; // optional
}
List<Edge> edges = new ArrayList<>();
Space Complexity: O(E) Applications: Kruskal's algorithm, graph input formats
| Criteria | Adjacency List | Adjacency Matrix |
|---|---|---|
| Graph density | Sparse graphs | Dense graphs |
| Edge check frequency | Rare | Frequent |
| Neighbor iteration | Required | Acceptable O(V) |
| Memory constraints | Critical | Relaxed |
| Dynamic changes | Frequent edge adds/deletes | Infrequent |
BFS explores graph level by level, using a queue. Finds shortest paths in unweighted graphs.
Algorithm:
function BFS(graph, start):
visited = array[graph.V] initialized to false
distance = array[graph.V] initialized to infinity
parent = array[graph.V] initialized to -1
queue = new Queue()
visited[start] = true
distance[start] = 0
queue.enqueue(start)
while not queue.isEmpty():
u = queue.dequeue()
for each v in graph.adj[u]:
if not visited[v]:
visited[v] = true
distance[v] = distance[u] + 1
parent[v] = u
queue.enqueue(v)
return distance, parent
Complexity:
- Time: O(V + E) with adjacency list
- Space: O(V) for queue and visited array
Properties:
- Finds shortest path in unweighted graphs
- Visits vertices in increasing distance order
- BFS tree has property that non-tree edges never connect vertices more than 1 level apart
Applications:
- Shortest path in unweighted graphs
- Web crawling
- Social network friend recommendations
- GPS navigation (simplified)
- Checking bipartiteness
- Connected components
BFS for bipartite checking:
function isBipartite(graph):
color = array[graph.V] initialized to -1
for each vertex v in graph.V:
if color[v] == -1:
if not BFSCheck(v):
return false
return true
function BFSCheck(start):
queue = new Queue()
queue.enqueue(start)
color[start] = 0
while not queue.isEmpty():
u = queue.dequeue()
for each v in graph.adj[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.enqueue(v)
else if color[v] == color[u]:
return false
return true
DFS explores as far as possible along each branch before backtracking, using stack (explicit or recursion).
Algorithm (recursive) :
function DFS(graph):
visited = array[graph.V] initialized to false
for each vertex v in graph.V:
if not visited[v]:
DFSVisit(v)
function DFSVisit(u):
visited[u] = true
// pre-order processing
for each v in graph.adj[u]:
if not visited[v]:
parent[v] = u
DFSVisit(v)
// post-order processing
Complexity: O(V + E) with adjacency list
DFS with timestamps (for topological sort, SCCs):
time = 0
function DFSVisit(u):
visited[u] = true
discovery[u] = ++time
for each v in graph.adj[u]:
if not visited[v]:
parent[v] = u
DFSVisit(v)
finish[u] = ++time
Edge classification:
- Tree edges: edges traversed during DFS
- Back edges: edges to ancestor (indicate cycles)
- Forward edges: edges to descendant in DFS tree
- Cross edges: edges between different subtrees
Applications:
- Topological sorting
- Strongly connected components
- Cycle detection
- Maze solving
- Path finding
- Solving puzzles with single solution
Cycle detection:
function hasCycle(graph):
visited = array[graph.V] initialized to false
recStack = array[graph.V] initialized to false // recursion stack
for each vertex v:
if hasCycleUtil(v, visited, recStack):
return true
return false
function hasCycleUtil(v, visited, recStack):
if not visited[v]:
visited[v] = true
recStack[v] = true
for each neighbor in graph.adj[v]:
if not visited[neighbor] and hasCycleUtil(neighbor, visited, recStack):
return true
else if recStack[neighbor]:
return true
recStack[v] = false
return false
return false
Linear ordering of vertices in directed acyclic graph (DAG) such that for every edge u→v, u appears before v.
Algorithm 1 (DFS-based) :
function topologicalSortDFS(graph):
visited = array[graph.V] initialized to false
stack = new Stack()
for each vertex v in graph.V:
if not visited[v]:
topologicalSortUtil(v, visited, stack)
return stack reversed order
function topologicalSortUtil(v, visited, stack):
visited[v] = true
for each neighbor in graph.adj[v]:
if not visited[neighbor]:
topologicalSortUtil(neighbor, visited, stack)
stack.push(v) // push after processing all neighbors
Algorithm 2 (Kahn's algorithm - BFS-based) :
function topologicalSortKahn(graph):
inDegree = array[graph.V] initialized to 0
for each vertex u:
for each v in graph.adj[u]:
inDegree[v]++
queue = new Queue()
for each vertex v:
if inDegree[v] == 0:
queue.enqueue(v)
result = []
while not queue.isEmpty():
u = queue.dequeue()
result.append(u)
for each v in graph.adj[u]:
inDegree[v]--
if inDegree[v] == 0:
queue.enqueue(v)
if result.length != graph.V:
error "Graph has cycle"
return result
Complexity: O(V + E)
Applications:
- Build systems (Makefile)
- Course prerequisite scheduling
- Dependency resolution
- Instruction scheduling in compilers
Connected components in undirected graphs:
function connectedComponents(graph):
visited = array[graph.V] initialized to false
components = []
componentId = 0
for each vertex v:
if not visited[v]:
component = []
dfsCollect(v, visited, component)
components.append(component)
componentId++
return components
function dfsCollect(v, visited, component):
visited[v] = true
component.append(v)
for each neighbor in graph.adj[v]:
if not visited[neighbor]:
dfsCollect(neighbor, visited, component)
Strongly Connected Components (SCC) in directed graphs: SCC is maximal set of vertices where every vertex reachable from every other.
Kosaraju's Algorithm:
function kosarajuSCC(graph):
// Step 1: DFS to get finish order
visited = array[graph.V] initialized to false
stack = new Stack()
for each vertex v:
if not visited[v]:
fillOrder(v, visited, stack)
// Step 2: Create transpose graph
transpose = createTranspose(graph)
// Step 3: DFS on transpose in stack order
visited = array[graph.V] initialized to false
sccs = []
while not stack.isEmpty():
v = stack.pop()
if not visited[v]:
component = []
dfsTranspose(transpose, v, visited, component)
sccs.append(component)
return sccs
function fillOrder(v, visited, stack):
visited[v] = true
for each neighbor in graph.adj[v]:
if not visited[neighbor]:
fillOrder(neighbor, visited, stack)
stack.push(v)
Tarjan's Algorithm (single DFS, more efficient):
function tarjanSCC(graph):
index = 0
stack = new Stack()
indices = array[graph.V] initialized to -1
lowlink = array[graph.V]
onStack = array[graph.V] initialized to false
sccs = []
for each vertex v:
if indices[v] == -1:
strongConnect(v)
return sccs
function strongConnect(v):
indices[v] = index
lowlink[v] = index
index++
stack.push(v)
onStack[v] = true
for each neighbor in graph.adj[v]:
if indices[neighbor] == -1:
strongConnect(neighbor)
lowlink[v] = min(lowlink[v], lowlink[neighbor])
else if onStack[neighbor]:
lowlink[v] = min(lowlink[v], indices[neighbor])
if lowlink[v] == indices[v]: // root of SCC
component = []
while true:
w = stack.pop()
onStack[w] = false
component.append(w)
if w == v:
break
sccs.append(component)
Complexity: O(V + E) for both algorithms
Applications:
- Social network analysis (communities)
- Web page clustering
- Circuit analysis
- Program analysis (call graphs)
Finds shortest paths from single source to all vertices in weighted graph with non-negative edges.
Algorithm:
function dijkstra(graph, source):
dist = array[graph.V] initialized to INFINITY
dist[source] = 0
visited = array[graph.V] initialized to false
parent = array[graph.V] initialized to -1
pq = new PriorityQueue() // (distance, vertex)
pq.add((0, source))
while not pq.isEmpty():
(d, u) = pq.poll()
if visited[u]: continue
visited[u] = true
for each (v, weight) in graph.adj[u]:
if not visited[v] and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
parent[v] = u
pq.add((dist[v], v))
return dist, parent
Complexity:
- With binary heap: O((V + E) log V)
- With Fibonacci heap: O(V log V + E)
Correctness proof (invariant): When vertex u is extracted from priority queue, dist[u] is final shortest distance.
Optimizations:
- Early termination: Stop when target reached
- Bidirectional Dijkstra: Search from both source and target
- A*: Add heuristic to guide search
Handles negative edge weights and detects negative cycles.
Algorithm:
function bellmanFord(graph, source):
dist = array[graph.V] initialized to INFINITY
dist[source] = 0
parent = array[graph.V] initialized to -1
// Relax edges V-1 times
for i = 1 to graph.V - 1:
for each edge (u, v, weight) in graph.edges:
if dist[u] != INFINITY and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
parent[v] = u
// Check for negative cycles
for each edge (u, v, weight) in graph.edges:
if dist[u] != INFINITY and dist[u] + weight < dist[v]:
error "Graph contains negative cycle"
return dist, parent
Complexity: O(V·E)
Applications:
- Currency arbitrage detection
- Network routing protocols (RIP)
- Graphs with negative weights
Finds shortest paths between all pairs of vertices.
Algorithm:
function floydWarshall(graph):
dist = array[graph.V][graph.V]
// Initialize
for i = 0 to graph.V-1:
for j = 0 to graph.V-1:
if i == j:
dist[i][j] = 0
else if graph.hasEdge(i, j):
dist[i][j] = graph.getWeight(i, j)
else:
dist[i][j] = INFINITY
// Main loop
for k = 0 to graph.V-1:
for i = 0 to graph.V-1:
for j = 0 to graph.V-1:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Complexity: Θ(V³) time, Θ(V²) space
Detecting negative cycles: If any dist[i][i] < 0 after algorithm, negative cycle exists.
Transitive closure (reachability): Replace min with OR, + with AND.
Applications:
- Finding transitive closure
- Computing inverse of matrix (in some contexts)
- Dense graph shortest paths
Combines Bellman-Ford and Dijkstra for all-pairs shortest paths in sparse graphs with possible negative weights.
Algorithm:
function johnson(graph):
// Add new vertex with zero-weight edges to all vertices
newVertex = graph.V
graph.addVertex()
for each vertex v in original graph:
graph.addEdge(newVertex, v, 0)
// Run Bellman-Ford from new vertex
h = bellmanFord(graph, newVertex)
if negative cycle detected:
error
// Reweight edges: w'(u,v) = w(u,v) + h[u] - h[v]
for each edge (u,v,weight):
newWeight = weight + h[u] - h[v]
graph.setWeight(u, v, newWeight)
// Run Dijkstra from each vertex
for each vertex u:
dist[u] = dijkstra(graph, u)
// Restore original distances
for each vertex v:
dist[u][v] = dist[u][v] + h[v] - h[u]
return dist
Complexity: O(V² log V + V·E) with binary heap
Heuristic-guided Dijkstra for finding path to specific target.
Algorithm:
function aStar(graph, source, target, heuristic):
openSet = new PriorityQueue() // f-score = g + h
gScore = array[graph.V] initialized to INFINITY
gScore[source] = 0
fScore = array[graph.V] initialized to INFINITY
fScore[source] = heuristic(source, target)
parent = array[graph.V] initialized to -1
openSet.add((fScore[source], source))
while not openSet.isEmpty():
(_, current) = openSet.poll()
if current == target:
return reconstructPath(parent, target)
for each (neighbor, weight) in graph.adj[current]:
tentative_g = gScore[current] + weight
if tentative_g < gScore[neighbor]:
parent[neighbor] = current
gScore[neighbor] = tentative_g
fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, target)
openSet.add((fScore[neighbor], neighbor))
return null // no path
Properties:
- Optimal if heuristic is admissible (never overestimates) and consistent
- Consistent: h(u) ≤ weight(u,v) + h(v) for all edges
Common heuristics:
- Euclidean distance (geometric graphs)
- Manhattan distance (grids)
- Diagonal distance (8-direction movement)
Applications:
- GPS navigation
- Video game pathfinding
- Robotics motion planning
- Puzzle solving (15-puzzle, Rubik's cube)
Greedy algorithm that builds MST by adding smallest edges that don't create cycles.
Algorithm:
function kruskalMST(graph):
edges = getAllEdges(graph)
sort edges by weight ascending
uf = new UnionFind(graph.V)
mst = []
for each edge (u, v, weight) in sorted edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append(edge)
if mst.length == graph.V - 1:
break
return mst
Complexity: O(E log E) for sorting + O(E α(V)) for union-find
Correctness: Cut property ensures greedy choice optimal
Applications:
- Network design (minimize cabling cost)
- Clustering algorithms
- Approximation for NP-hard problems
Greedy algorithm that grows MST from starting vertex.
Algorithm:
function primMST(graph):
key = array[graph.V] initialized to INFINITY
key[0] = 0
parent = array[graph.V] initialized to -1
inMST = array[graph.V] initialized to false
pq = new PriorityQueue() // (key, vertex)
pq.add((0, 0))
while not pq.isEmpty():
u = pq.poll().vertex
inMST[u] = true
for each (v, weight) in graph.adj[u]:
if not inMST[v] and weight < key[v]:
key[v] = weight
parent[v] = u
pq.add((key[v], v))
return parent
Complexity:
- With binary heap: O(E log V)
- With Fibonacci heap: O(E + V log V)
Comparison with Kruskal:
- Prim better for dense graphs
- Kruskal better for sparse graphs
- Kruskal requires sorting all edges
Oldest MST algorithm, works well for parallel implementation.
Algorithm:
function boruvkaMST(graph):
uf = new UnionFind(graph.V)
mst = []
while mst.length < graph.V - 1:
cheapest = array[graph.V] initialized to null
// Find cheapest edge from each component
for each edge (u, v, weight) in graph.edges:
rootU = uf.find(u)
rootV = uf.find(v)
if rootU != rootV:
if cheapest[rootU] == null or
weight < cheapest[rootU].weight:
cheapest[rootU] = edge
if cheapest[rootV] == null or
weight < cheapest[rootV].weight:
cheapest[rootV] = edge
// Add cheapest edges for each component
for each vertex v:
if cheapest[v] != null:
u = cheapest[v].u
w = cheapest[v].v
if uf.find(u) != uf.find(w):
uf.union(u, w)
mst.append(cheapest[v])
return mst
Complexity: O(E log V) (each iteration halves components)
Applications: Distributed computing, parallel MST algorithms
Cut property: For any cut, minimum weight crossing edge belongs to some MST.
Cycle property: For any cycle, maximum weight edge cannot be in any MST.
Uniqueness: If all edge weights distinct, MST is unique.
Finds maximum flow in flow network using augmenting paths.
Basic algorithm:
function fordFulkerson(graph, source, sink):
residual = copy graph // create residual graph
maxFlow = 0
while exists path p from source to sink in residual:
// Find bottleneck capacity
bottleneck = min(residual(u,v) for (u,v) in p)
// Augment flow
for each (u,v) in p:
residual[u][v] -= bottleneck
residual[v][u] += bottleneck // reverse edge
maxFlow += bottleneck
return maxFlow
Complexity: O(E·|f*|) where |f*| is maximum flow value (can be exponential)
Path finding: Can use BFS (Edmonds-Karp) or DFS
Ford-Fulkerson with BFS for shortest augmenting paths.
Algorithm:
function edmondsKarp(graph, source, sink):
residual = copy graph
maxFlow = 0
parent = array[graph.V]
while bfs(residual, source, sink, parent):
// Find bottleneck
pathFlow = INFINITY
v = sink
while v != source:
u = parent[v]
pathFlow = min(pathFlow, residual[u][v])
v = u
// Update residual network
v = sink
while v != source:
u = parent[v]
residual[u][v] -= pathFlow
residual[v][u] += pathFlow
v = u
maxFlow += pathFlow
return maxFlow
function bfs(residual, source, sink, parent):
visited = array[residual.V] initialized to false
queue = new Queue()
queue.enqueue(source)
visited[source] = true
parent[source] = -1
while not queue.isEmpty():
u = queue.dequeue()
for each v in residual.V:
if not visited[v] and residual[u][v] > 0:
visited[v] = true
parent[v] = u
queue.enqueue(v)
if v == sink:
return true
return false
Complexity: O(V·E²)
Properties:
- Each BFS finds shortest augmenting path
- Number of augmentations ≤ O(V·E)
Uses level graph and blocking flows for efficiency.
Algorithm:
function dinic(graph, source, sink):
residual = copy graph
maxFlow = 0
while bfs(residual, source, sink):
level = computeLevels(residual, source, sink)
ptr = array[residual.V] initialized to 0
while flow = dfs(residual, source, sink, INFINITY, level, ptr):
maxFlow += flow
return maxFlow
function dfs(residual, u, sink, flow, level, ptr):
if u == sink:
return flow
for i = ptr[u] to residual.V-1:
if residual[u][i] > 0 and level[i] == level[u] + 1:
pushed = dfs(residual, i, sink, min(flow, residual[u][i]), level, ptr)
if pushed > 0:
residual[u][i] -= pushed
residual[i][u] += pushed
return pushed
ptr[u]++
return 0
Complexity: O(V²·E) worst case, O(min(V^(2/3), √E)·E) for unit capacities
Optimizations:
- Scaling: push larger flows first
- Dynamic trees: O(E log V)
Alternative approach using preflow and excess.
Algorithm concept:
- Maintain excess at vertices
- Push flow from vertices with excess to neighbors at lower height
- Relabel (increase height) when stuck
function pushRelabel(graph, source, sink):
// Initialize
height = array[graph.V] initialized to 0
excess = array[graph.V] initialized to 0
height[source] = graph.V
for each v adjacent to source:
flow = graph[source][v]
excess[source] -= flow
excess[v] += flow
residual[source][v] -= flow
residual[v][source] += flow
// Main loop
while exists active vertex (excess > 0 and not source/sink):
u = any active vertex
// Try to push
pushed = false
for each v with residual[u][v] > 0:
if height[u] == height[v] + 1:
delta = min(excess[u], residual[u][v])
residual[u][v] -= delta
residual[v][u] += delta
excess[u] -= delta
excess[v] += delta
pushed = true
break
if not pushed:
// Relabel
height[u] = 1 + min(height[v] for v with residual[u][v] > 0)
return excess[sink]
Complexity: O(V³) with FIFO selection,
Find flow of given value with minimum cost.
Successive Shortest Path Algorithm:
function minCostMaxFlow(graph, source, sink, requiredFlow):
flow = 0
cost = 0
potential = array[graph.V] initialized to 0
residual = copy graph
while flow < requiredFlow:
// Find shortest path in residual using reduced costs
dist, parent = shortestPath(residual, source, sink, potential)
if dist[sink] == INFINITY:
return null // impossible
// Update potentials
for i = 0 to graph.V-1:
if dist[i] < INFINITY:
potential[i] += dist[i]
// Find bottleneck
bottleneck = requiredFlow - flow
v = sink
while v != source:
u = parent[v]
bottleneck = min(bottleneck, residual[u][v])
v = u
// Augment
v = sink
while v != source:
u = parent[v]
residual[u][v] -= bottleneck
residual[v][u] += bottleneck
cost += bottleneck * getCost(u, v) // original cost
v = u
flow += bottleneck
return cost
Complexity:
Theorem: Maximum flow value equals minimum cut capacity.
Cut: Partition of vertices into S and T with source in S, sink in T Cut capacity: Sum of capacities from S to T
Applications:
- Image segmentation
- Project selection
- Bipartite matching
- Edge connectivity
Already covered in 22.4. Applications include:
- Web graph analysis (SCCs as communities)
- Program optimization (loops detection)
- Social network analysis
Maximum matching in bipartite graphs.
Kőnig's Theorem: In bipartite graphs, size of maximum matching = size of minimum vertex cover
Hopcroft-Karp Algorithm:
function hopcroftKarp(graph, leftSet, rightSet):
matchL = array[leftSet] initialized to -1
matchR = array[rightSet] initialized to -1
dist = array[leftSet]
matching = 0
while bfs():
for each u in leftSet:
if matchL[u] == -1 and dfs(u):
matching++
return matching
function bfs():
queue = new Queue()
for each u in leftSet:
if matchL[u] == -1:
dist[u] = 0
queue.enqueue(u)
else:
dist[u] = INFINITY
found = false
while not queue.isEmpty():
u = queue.dequeue()
for each v in graph.adj[u]:
if matchR[v] != -1 and dist[matchR[v]] == INFINITY:
dist[matchR[v]] = dist[u] + 1
queue.enqueue(matchR[v])
else if matchR[v] == -1:
found = true
return found
function dfs(u):
for each v in graph.adj[u]:
if matchR[v] == -1 or (dist[matchR[v]] == dist[u] + 1 and dfs(matchR[v])):
matchL[u] = v
matchR[v] = u
return true
dist[u] = INFINITY
return false
Complexity: O(√V·E)
Solves assignment problem: minimum weight matching in bipartite graph.
Algorithm:
function hungarian(cost):
n = cost.length
u = array[n+1] // potentials for rows
v = array[n+1] // potentials for columns
p = array[n+1] // matching for columns
way = array[n+1]
for i = 1 to n:
p[0] = i
j0 = 0
minv = array[n+1] initialized to INFINITY
used = array[n+1] initialized to false
while true:
used[j0] = true
i0 = p[j0]
delta = INFINITY
j1 = 0
for j = 1 to n:
if not used[j]:
cur = cost[i0-1][j-1] - u[i0] - v[j]
if cur < minv[j]:
minv[j] = cur
way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
for j = 0 to n:
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0:
break
while true:
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
if j0 == 0:
break
return (-v[0], p) // minimum cost and assignment
Complexity: O(n³)
Assign colors to vertices such that adjacent vertices have different colors.
Greedy coloring:
function greedyColoring(graph):
result = array[graph.V] initialized to -1
result[0] = 0
for u = 1 to graph.V-1:
used = array[graph.V] initialized to false
for each v in graph.adj[u]:
if result[v] != -1:
used[result[v]] = true
for color = 0 to graph.V-1:
if not used[color]:
result[u] = color
break
return result
Chromatic number: Minimum colors needed (NP-hard to find optimally)
Applications:
- Register allocation in compilers
- Scheduling problems
- Map coloring
Graphs that can be drawn without edge intersections.
Properties:
- Euler's formula: V - E + F = 2 for connected planar graphs
- Max edges: E ≤ 3V - 6 (V ≥ 3)
- Kuratowski's theorem: Non-planar iff contains K₅ or K₃,₃ subdivision
Applications:
- Circuit layout
- Geographic information systems
- Graph visualization
Eulerian path: Visits every edge exactly once
- Exists iff 0 or 2 vertices have odd degree
- Hierholzer's algorithm finds in O(E)
Hamiltonian path: Visits every vertex exactly once
- NP-complete to find
- Dirac's theorem: If every vertex degree ≥ n/2, Hamiltonian cycle exists
Applications:
- Route planning
- DNA sequencing
- Puzzle solving
Divide and conquer breaks problem into smaller subproblems, solves them recursively, and combines results.
General structure:
function divideAndConquer(problem):
if problem is trivial:
return solveDirectly(problem)
subproblems = divide(problem)
for each subproblem in subproblems:
subresults.append(divideAndConquer(subproblem))
return combine(subresults)
Key steps:
- Divide: Partition into independent subproblems
- Conquer: Solve subproblems recursively
- Combine: Merge subproblem solutions
Already covered in 2.3. Applies to recurrences of form T(n) = aT(n/b) + f(n).
Merge Sort (already covered):
- Divide: Split array into halves
- Conquer: Sort each half recursively
- Combine: Merge sorted halves
Quick Sort (already covered):
- Divide: Partition around pivot
- Conquer: Sort partitions recursively
- Combine: Trivial (in-place)
Binary Search (already covered):
- Divide: Compare with middle element
- Conquer: Search appropriate half
- Combine: Trivial
Strassen's Matrix Multiplication:
- Divide: Split 2n×2n matrices into n×n blocks
- Conquer: Compute 7 products recursively
- Combine: Add/subtract products for result
- Complexity: O(n^2.807) (vs O(n³) naive)
Karatsuba Multiplication:
- Multiply two n-digit numbers
- Split into high and low halves
- Compute three products recursively
- Complexity: O(n^1.585) (vs O(n²) naive)
Closest Pair of Points:
- Divide: Sort by x-coordinate, split at median
- Conquer: Find closest pairs in left and right
- Combine: Check points within strip of width min distance
- Complexity: O(n log n)
Greedy algorithms make locally optimal choice at each step, hoping for global optimum.
Properties required for optimality:
- Greedy choice property: Locally optimal choice leads to globally optimal solution
- Optimal substructure: Optimal solution contains optimal solutions to subproblems
Select maximum number of non-overlapping activities.
Problem: Activities with start and finish times (sᵢ, fᵢ) Greedy strategy: Always pick activity with earliest finish time
function activitySelection(activities):
sort activities by finish time
result = [activities[0]]
lastFinish = activities[0].finish
for i = 1 to activities.length-1:
if activities[i].start ≥ lastFinish:
result.append(activities[i])
lastFinish = activities[i].finish
return result
Complexity: O(n log n) for sorting Optimality proof: Exchange argument shows any optimal solution can be transformed to greedy solution
Optimal prefix-free code for data compression.
Algorithm:
function huffmanCoding(characters, frequencies):
pq = new PriorityQueue() // min-heap of trees
for each character:
pq.add(new Node(char, freq))
while pq.size() > 1:
left = pq.poll()
right = pq.poll()
parent = new Node(null, left.freq + right.freq)
parent.left = left
parent.right = right
pq.add(parent)
root = pq.poll()
return generateCodes(root, "")
Complexity: O(n log n)
Properties: Produces optimal prefix code (proof by greedy stays ahead)
Matroids provide theoretical foundation for greedy optimality.
Definition: A matroid (E, I) where:
- E is finite set
- I is collection of independent subsets
- Hereditary property: If A ∈ I and B ⊆ A, then B ∈ I
- Exchange property: If A,B ∈ I and |A| < |B|, then ∃x ∈ B\A with A ∪ {x} ∈ I
Greedy algorithm on matroids: Sort elements by weight descending, add if set remains independent
Examples:
- Graphic matroid: Forests in graph
- Uniform matroid: All subsets of size ≤ k
Why greedy works on matroids: Exchange property ensures greedy picks optimal basis
Top-down approach: recursively solve with caching.
function fib(n):
if memo[n] exists:
return memo[n]
if n ≤ 1:
return n
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
Bottom-up approach: fill table iteratively.
function fib(n):
dp = array[n+1]
dp[0] = 0
dp[1] = 1
for i = 2 to n:
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
0/1 Knapsack:
function knapsack01(values, weights, capacity):
n = values.length
dp = array[n+1][capacity+1] initialized to 0
for i = 1 to n:
for w = 1 to capacity:
if weights[i-1] ≤ w:
dp[i][w] = max(dp[i-1][w],
dp[i-1][w - weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
Space optimization: Use 1D array, iterate backwards.
Unbounded Knapsack:
function unboundedKnapsack(values, weights, capacity):
dp = array[capacity+1] initialized to 0
for w = 1 to capacity:
for i = 0 to n-1:
if weights[i] ≤ w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
function lcs(X, Y):
m = X.length, n = Y.length
dp = array[m+1][n+1] initialized to 0
for i = 1 to m:
for j = 1 to n:
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])
// Reconstruct
lcs = []
i = m, j = n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs.prepend(X[i-1])
i--; j--
else if dp[i-1][j] > dp[i][j-1]:
i--
else:
j--
return dp[m][n], lcs
Complexity: O(mn)
Find optimal parenthesization to minimize multiplications.
function matrixChainOrder(dimensions):
n = dimensions.length - 1
dp = array[n][n] initialized to 0
bracket = array[n][n] // for reconstruction
for length = 2 to n:
for i = 0 to n-length:
j = i + length - 1
dp[i][j] = INFINITY
for k = i to j-1:
cost = dp[i][k] + dp[k+1][j] +
dimensions[i]*dimensions[k+1]*dimensions[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
bracket[i][j] = k
return dp[0][n-1], bracket
Complexity: O(n³)
Divide and Conquer Optimization: For dp[i][j] = min(dp[i-1][k-1] + C[k][j]) where C satisfies quadrangle inequality
Knuth Optimization: When optimal k is monotonic, reduces from O(n³) to O(n²)
Convex Hull Trick: For dp[i] = min/max(a[j]·x[i] + b[j]), maintain convex hull of lines
Bitmask DP: For subset problems: dp[mask] representing state of chosen elements
Place N queens on N×N board such that no two attack each other.
function solveNQueens(n):
result = []
board = array[n] initialized to -1 // board[row] = column
backtrack(result, board, 0, n)
return result
function backtrack(result, board, row, n):
if row == n:
result.add(board copy)
return
for col = 0 to n-1:
if isValid(board, row, col):
board[row] = col
backtrack(result, board, row+1, n)
board[row] = -1 // undo
function isValid(board, row, col):
for i = 0 to row-1:
if board[i] == col or // same column
board[i] - i == col - row or // diagonal \
board[i] + i == col + row: // diagonal /
return false
return true
Complexity: O(n!) worst case, but pruning reduces significantly
Find subsets that sum to target.
function subsetSum(numbers, target):
result = []
current = []
backtrack(result, current, numbers, target, 0)
return result
function backtrack(result, current, numbers, remaining, start):
if remaining == 0:
result.add(current copy)
return
for i = start to numbers.length-1:
if numbers[i] > remaining:
continue
if i > start and numbers[i] == numbers[i-1]:
continue // skip duplicates
current.append(numbers[i])
backtrack(result, current, numbers, remaining - numbers[i], i+1)
current.pop()
General framework for problems with constraints.
Sudoku solver:
function solveSudoku(board):
empty = findEmptyCell(board)
if not empty:
return true // solved
(row, col) = empty
for num = 1 to 9:
if isValid(board, row, col, num):
board[row][col] = num
if solveSudoku(board):
return true
board[row][col] = 0 // backtrack
return false
Applications:
- Crossword puzzles
- Map coloring
- Scheduling
- Cryptarithmetic puzzles
Branch and bound systematically enumerates candidates while pruning using bounds.
Components:
- Branching: Split problem into subproblems
- Bounding: Compute optimistic bound for subproblem
- Pruning: Discard if bound worse than best known
General algorithm:
function branchAndBound(problem):
best = INFINITY
bestSolution = null
queue = new PriorityQueue() // ordered by bound
queue.add(problem)
while not queue.isEmpty():
node = queue.poll()
if node.bound ≥ best:
continue // prune
if node.isSolution():
if node.value < best:
best = node.value
bestSolution = node.solution
else:
for child in node.branch():
child.bound = computeBound(child)
if child.bound < best:
queue.add(child)
return bestSolution
Common bounding techniques:
- Relaxation (LP relaxation)
- Greedy bounds
- Lagrangian relaxation
Find shortest Hamiltonian cycle.
Branch and bound for TSP:
function tspBranchBound(graph):
n = graph.V
best = INFINITY
bestPath = null
visited = array[n] initialized to false
visited[0] = true
currentPath = [0]
tspRecursive(0, 0, 1, visited, currentPath)
return bestPath
function tspRecursive(currentNode, currentCost, visitedCount, visited, path):
if visitedCount == n:
totalCost = currentCost + graph[currentNode][0]
if totalCost < best:
best = totalCost
bestPath = path + [0]
return
// Compute bound
bound = currentCost + computeLowerBound(visited)
if bound ≥ best:
return // prune
for nextNode = 0 to n-1:
if not visited[nextNode]:
visited[nextNode] = true
path.append(nextNode)
tspRecursive(nextNode, currentCost + graph[currentNode][nextNode],
visitedCount + 1, visited, path)
path.pop()
visited[nextNode] = false
function computeLowerBound(visited):
// MST-based bound: sum of MST of unvisited + connections
// Held-Karp lower bound using 1-trees
Applications:
- Vehicle routing
- Circuit board drilling
- Genome sequencing
Las Vegas: Always correct, running time random
- Example: Randomized QuickSort (always sorts, time varies)
- Analysis: Expected time bounds
Monte Carlo: May err, fixed running time
- Example: Freivalds' matrix multiplication check
- Analysis: Probability of error bounds
Already covered. Expected time O(n log n) with random pivot.
Randomized selection (QuickSelect): Expected O(n), worst O(n²)
Karger's algorithm for global minimum cut.
Algorithm:
function kargerMinCut(graph):
while graph.V > 2:
// Pick random edge
(u,v) = randomEdge(graph)
// Contract edge u-v
mergeVertices(graph, u, v)
// Remove self-loops
// Remaining edges form cut
return graph.edges.count
Analysis:
- Probability of finding specific min cut ≥ 1/C(n,2)
- Run O(n² log n) times for high probability
- Total O(n⁴ log n) time
Optimized version: O(n² log³ n) using recursive approach
Check matrix multiplication: A×B = C
Algorithm:
function freivalds(A, B, C, k):
n = A.rows
for i = 1 to k:
r = randomVector(n) // entries 0 or 1
if A*(B*r) != C*r:
return false
return true
Properties:
- If A×B = C, always returns true
- If A×B ≠ C, probability of error ≤ 2^(-k)
- Time O(k·n²)
Technique to prove existence using probability.
Example: Large cuts in graphs
- Random partition gives expected cut size ≥ |E|/2
- Therefore some cut has size ≥ |E|/2
- Derandomizable using conditional expectations
For minimization: ALG ≤ α·OPT For maximization: ALG ≥ OPT/α
α: approximation factor (≥ 1 for minimization, ≤ 1 for maximization)
Problem: Minimum set of vertices covering all edges
Greedy 2-approximation:
function approxVertexCover(graph):
covered = empty set
edges = graph.edges copy
while edges not empty:
(u,v) = any edge in edges
covered.add(u)
covered.add(v)
remove all edges incident to u or v from edges
return covered
Proof: Greedy picks both endpoints, OPT must pick at least one per chosen edge
Better bounds: Using LP relaxation gives 2-approximation
Problem: Cover universe with fewest sets from collection
Greedy algorithm:
function setCover(universe, sets):
covered = empty set
result = empty set
remaining = universe copy
while remaining not empty:
// Pick set covering most uncovered elements
bestSet = argmax(|set ∩ remaining|)
result.add(bestSet)
covered = covered ∪ bestSet
remaining = remaining \ bestSet
return result
Analysis: H_n-approximation where H_n is harmonic number
Hardness: Cannot approximate better than (1 - ε) ln n unless P = NP
Metric TSP (satisfies triangle inequality):
- MST-based 2-approximation: Build MST, traverse with shortcuts
- Christofides algorithm: 1.5-approximation
- Build MST
- Find minimum perfect matching on odd-degree vertices
- Combine to form Eulerian graph
- Find Eulerian tour, take shortcuts
General TSP: No constant-factor approximation unless P = NP
FPTAS (Fully Polynomial-Time Approximation Scheme):
- Scale values, run DP
- For any ε > 0, finds (1-ε)-approximation
- Time O(n³/ε)
Linear-time pattern matching using failure function.
Algorithm:
function KMP(text, pattern):
// Build failure function
lps = computeLPS(pattern)
i = 0 // index for text
j = 0 // index for pattern
matches = []
while i < text.length:
if pattern[j] == text[i]:
i++
j++
if j == pattern.length:
matches.add(i - j)
j = lps[j-1]
else if i < text.length and pattern[j] != text[i]:
if j != 0:
j = lps[j-1]
else:
i++
return matches
function computeLPS(pattern):
lps = array[pattern.length] initialized to 0
len = 0 // length of previous longest prefix suffix
i = 1
while i < pattern.length:
if pattern[i] == pattern[len]:
len++
lps[i] = len
i++
else:
if len != 0:
len = lps[len-1]
else:
lps[i] = 0
i++
return lps
Complexity: O(n + m) time, O(m) space
Uses rolling hash for pattern matching.
Algorithm:
function rabinKarp(text, pattern):
n = text.length
m = pattern.length
base = 256
prime = large prime
// Precompute hash
h = 1
for i = 1 to m-1:
h = (h * base) % prime
// Compute pattern hash
patternHash = 0
for i = 0 to m-1:
patternHash = (patternHash * base + pattern[i]) % prime
// Compute first window hash
textHash = 0
for i = 0 to m-1:
textHash = (textHash * base + text[i]) % prime
matches = []
for i = 0 to n-m:
if patternHash == textHash:
if text.substring(i, i+m) == pattern:
matches.add(i)
if i < n-m:
textHash = (base * (textHash - text[i] * h) + text[i+m]) % prime
if textHash < 0:
textHash += prime
return matches
Complexity: Average O(n+m), worst O(nm) Applications: Multiple pattern matching, plagiarism detection
Computes Z-array: longest substring starting at i matching prefix.
Algorithm:
function zAlgorithm(s):
n = s.length
Z = array[n] initialized to 0
l = r = 0
for i = 1 to n-1:
if i ≤ r:
Z[i] = min(r - i + 1, Z[i - l])
while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:
Z[i]++
if i + Z[i] - 1 > r:
l = i
r = i + Z[i] - 1
return Z
Applications:
- Pattern matching: concatenate pattern + "$" + text
- Find all occurrences: O(n+m)
- String compression detection
Efficient pattern matching using bad character and good suffix heuristics.
Bad character rule: When mismatch at text[i] and pattern[j], shift so that text[i] aligns with last occurrence in pattern.
Good suffix rule: When suffix matches, shift to align with previous occurrence.
Complexity: Sublinear on average, O(nm) worst but rarely reaches
Smallest convex polygon containing all points.
Graham Scan:
function convexHull(points):
// Find lowest y (leftmost if tie)
start = point with minimum y
// Sort by polar angle from start
sort points by angle from start
stack = new Stack()
stack.push(points[0])
stack.push(points[1])
for i = 2 to points.length-1:
while stack.size ≥ 2 and
crossProduct(stack[-2], stack[-1], points[i]) ≤ 0:
stack.pop()
stack.push(points[i])
return stack
function crossProduct(o, a, b):
return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x)
Complexity: O(n log n)
Jarvis March (Gift Wrapping) :
- Start with lowest point
- Repeatedly find point with smallest polar angle
- O(nh) where h is hull size
Process events in order of x-coordinate.
Line segment intersection:
function findIntersections(segments):
events = []
for each segment:
events.add(Event(segment.left, "add", segment))
events.add(Event(segment.right, "remove", segment))
sort events by x
active = new BalancedTree() // ordered by y
for event in events:
if event.type == "add":
// Check with neighbors in active
checkIntersections(segment, active)
active.add(segment)
else:
active.remove(segment)
Complexity: O((n + k) log n) where k = number of intersections
Find minimum distance between any two points.
Divide and conquer algorithm:
function closestPair(points):
sort points by x
return closestPairRecursive(points, 0, points.length-1)
function closestPairRecursive(points, left, right):
if right - left ≤ 3:
return bruteForce(points, left, right)
mid = (left + right) // 2
midX = points[mid].x
dL = closestPairRecursive(points, left, mid)
dR = closestPairRecursive(points, mid+1, right)
d = min(dL, dR)
// Find points within strip of width d
strip = []
for i = left to right:
if abs(points[i].x - midX) < d:
strip.append(points[i])
sort strip by y
for i = 0 to strip.length-1:
for j = i+1 to strip.length-1 and
strip[j].y - strip[i].y < d:
d = min(d, distance(strip[i], strip[j]))
return d
Complexity: O(n log n)
Ray casting algorithm:
function pointInPolygon(point, polygon):
inside = false
n = polygon.length
for i = 0 to n-1:
j = (i+1) % n
if ((polygon[i].y > point.y) != (polygon[j].y > point.y)):
xIntersect = polygon[i].x + (point.y - polygon[i].y) *
(polygon[j].x - polygon[i].x) /
(polygon[j].y - polygon[i].y)
if xIntersect < point.x:
inside = !inside
return inside
Complexity: O(n)
Parallel Random Access Machine with shared memory.
Parallel sum (tree reduction) :
parallelSum(array):
n = array.length
for step = 1 to log2(n):
for i = 0 to n-1 step 2^step in parallel:
array[i] += array[i + 2^(step-1)]
return array[0]
Work: O(n), Time: O(log n)
Programming model for distributed processing.
Word count example:
map(String key, String value):
// key: document name, value: document contents
for each word w in value:
emitIntermediate(w, "1")
reduce(String key, List values):
// key: a word, values: list of counts
int result = 0
for each v in values:
result += Integer.parseInt(v)
emit(key, result)
Odd-Even Transposition Sort:
parallelOddEvenSort(array):
n = array.length
for phase = 0 to n-1:
if phase % 2 == 0:
// Even phase: compare-exchange (0,1), (2,3), ...
for i = 0 to n-2 step 2 in parallel:
if array[i] > array[i+1]:
swap(array[i], array[i+1])
else:
// Odd phase: compare-exchange (1,2), (3,4), ...
for i = 1 to n-2 step 2 in parallel:
if array[i] > array[i+1]:
swap(array[i], array[i+1])
Complexity: O(n) time with n/2 processors
Bitonic Sort: O(log² n) time with O(n log² n) work
Pregel model (vertex-centric):
- Superstep computation
- Vertices send messages to neighbors
- Synchronization between supersteps
PageRank in Pregel:
function compute(vertex, messages):
if superstep == 0:
vertex.value = 1.0 / totalVertices
else:
sum = 0
for msg in messages:
sum += msg
vertex.value = 0.15 / totalVertices + 0.85 * sum
if superstep < maxIterations:
for neighbor in vertex.outgoing:
sendMessage(neighbor, vertex.value / vertex.outDegree)
else:
voteToHalt()
Memory hierarchy with:
- M: main memory size (words)
- B: block size (words)
- I/O: transfer between disk and memory
Aggarwal-Vitter model: Count number of block transfers
Already covered. B-trees minimize I/O by ensuring each node fits in block.
External sorting:
- Phase 1: Create sorted runs of size M
- Phase 2: Merge runs using heap
- I/O complexity:
$O((n/B) log_{M/B} (n/B))$
Algorithms designed without knowledge of cache parameters that perform well on any memory hierarchy.
Cache-oblivious matrix multiplication:
function multiply(A, B, C, n):
if n ≤ threshold:
// Base case: standard multiplication
for i, j, k:
C[i][j] += A[i][k] * B[k][j]
else:
// Divide matrices into blocks
n2 = n/2
multiply(A11, B11, C11, n2)
multiply(A11, B12, C12, n2)
multiply(A21, B11, C21, n2)
multiply(A21, B12, C22, n2)
multiply(A12, B21, C11, n2)
multiply(A12, B22, C12, n2)
multiply(A22, B21, C21, n2)
multiply(A22, B22, C22, n2)
Cache-oblivious B-tree: Use van Emde Boas layout
Probabilistic data structure for frequency estimation.
Structure:
- d rows, w counters each
- d hash functions h₁...h_d
Update(x, count) :
for i = 1 to d:
sketch[i][h_i(x) % w] += count
Query(x) :
return min(sketch[i][h_i(x) % w] for i = 1 to d)
Properties:
- Space O(d·w)
- Overestimates (never underestimates)
- Error ≤ ε·N with probability 1-δ if w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉
Already covered in 7.6.
Sample k items uniformly from stream of unknown length.
Algorithm:
function reservoirSample(stream, k):
reservoir = array[k]
// Fill reservoir with first k items
for i = 0 to k-1:
reservoir[i] = stream.next()
// Process remaining items
i = k
while stream.hasNext():
item = stream.next()
j = random(0, i) // inclusive
if j < k:
reservoir[j] = item
i++
return reservoir
Proof: Each item has probability k/n of being in sample
Find items appearing more than n/k times.
Algorithm:
function misraGries(stream, k):
counters = empty map
for item in stream:
if item in counters:
counters[item]++
else if |counters| < k-1:
counters[item] = 1
else:
for each key in counters:
counters[key]--
if counters[key] == 0:
remove key
return counters.keys() // candidates for frequent items
Public-key cryptosystem based on factoring difficulty.
Key generation:
- Choose large primes p, q
- Compute n = p·q, φ(n) = (p-1)(q-1)
- Choose e with 1 < e < φ(n), gcd(e, φ(n)) = 1
- Compute d = e⁻¹ mod φ(n)
- Public key: (n, e), Private key: d
Encryption: c = m^e mod n Decryption: m = c^d mod n
Security: Based on difficulty of factoring n
Uses algebraic structure of elliptic curves over finite fields.
Curve equation: y² = x³ + ax + b mod p
Operations:
- Point addition
- Point doubling
- Scalar multiplication (k·P)
Security: Based on elliptic curve discrete logarithm problem
Advantages: Smaller keys than RSA for equivalent security
Properties: Preimage resistance, second preimage resistance, collision resistance
SHA-256:
- Merkle-Damgård construction
- Processes 512-bit blocks
- Produces 256-bit hash
Applications:
- Digital signatures
- Password storage
- Integrity verification
- Blockchain
P: Problems solvable in polynomial time NP: Problems verifiable in polynomial time
Open question: Is P = NP? (Most believe P ≠ NP)
Problems in NP to which all NP problems reduce.
Cook-Levin Theorem: SAT is NP-complete
Classic NP-complete problems:
- 3-SAT
- Traveling Salesman Problem (decision version)
- Vertex Cover
- Clique
- Independent Set
- Hamiltonian Cycle
- Subset Sum
- Graph Coloring
Mapping problem A to problem B: A ≤_p B
Polynomial-time reduction: If B solvable in P, then A solvable in P
To prove NP-completeness:
- Show problem in NP
- Reduce known NP-complete problem to it
Every NP problem reduces to SAT in polynomial time.
Proof idea: Encode Turing machine computation as Boolean formula
Problems solvable with polynomial space.
PSPACE-complete problems:
- Quantified Boolean Formula (QBF)
- Generalized geography
- Go (with certain rules)
Relationship: P ⊆ NP ⊆ PSPACE, but unknown if proper
Tools:
- gprof (GNU profiler)
- Valgrind (memory profiling)
- perf (Linux performance counters)
- VTune (Intel)
Profiling steps:
- Identify hotspots (functions consuming most time)
- Analyze call graphs
- Measure cache misses, branch mispredictions
- Profile with representative inputs
Techniques:
- Structure packing: Reorder fields to minimize padding
- Custom allocators: Pool allocators for fixed-size objects
- Cache alignment: Align data to cache line boundaries
- Prefetching: Explicit cache prefetch instructions
Example: cache-friendly linked list:
struct Node {
int data;
int next; // index in array, not pointer
};
Node nodes[MAX_NODES]; // contiguous storage
Loop tiling (blocking):
for (ii = 0; ii < N; ii += BLOCK)
for (jj = 0; jj < N; jj += BLOCK)
for (kk = 0; kk < N; kk += BLOCK)
for (i = ii; i < min(ii+BLOCK, N); i++)
for (j = jj; j < min(jj+BLOCK, N); j++)
for (k = kk; k < min(kk+BLOCK, N); k++)
C[i][j] += A[i][k] * B[k][j];
Best practices:
- Warm-up runs to stabilize JIT/caches
- Multiple runs for statistical significance
- Monitor system load during benchmarks
- Report mean, median, standard deviation
- Use appropriate input sizes
Hoare logic:
- {P} program {Q} means if P holds before execution, Q holds after
Loop invariant:
- Must hold before loop, after each iteration, and after loop
Example (binary search) :
// Precondition: array sorted ascending
{ sorted(A) ∧ 0 ≤ low ≤ high < n }
while low ≤ high:
// Invariant: target in A[low..high] if present
mid = (low + high) // 2
if A[mid] == target:
return mid
else if A[mid] < target:
low = mid + 1
else:
high = mid - 1
// Postcondition: target not found
Generate random inputs and verify properties.
QuickCheck (Haskell) :
prop_revRev xs = reverse (reverse xs) == xs
where types = xs :: [Int]
Properties for algorithms:
- Sorting: result sorted, permutation of input
- Search: found iff present in input
- Data structures: invariants hold after operations
Generate random inputs to find bugs/crashes.
Mutation-based fuzzing:
- Start with seed inputs
- Mutate (bit flips, insertions, deletions)
- Monitor for crashes or invariant violations
Coverage-guided fuzzing (AFL):
- Track code coverage
- Prioritize inputs that explore new paths
Google's architecture:
- Crawling: Distributed crawlers with politeness policies
- Indexing: Inverted index with compression
- Ranking: PageRank + machine learning models
- Query processing: Query expansion, spell correction
- Caching: Results, inverted lists, documents
B+ trees in MySQL InnoDB:
- Primary key as clustered index
- Secondary indexes store primary key references
- Page size 16KB
- Adaptive hash indexes for hot pages
LSM trees in LevelDB/Cassandra:
- Memtables (in-memory)
- SSTables (sorted on disk)
- Compaction merges levels
- Bloom filters reduce I/O
Bitcoin:
- Merkle trees for transaction summaries
- Proof of Work (SHA-256)
- Unspent Transaction Outputs (UTXO) set
Ethereum:
- Merkle Patricia trie for state storage
- Account-based model
- Gas metering for computation
Linux Completely Fair Scheduler (CFS) :
- Red-black tree of tasks ordered by virtual runtime
- Pick leftmost (smallest vruntime)
- Fair share across processes
Real-time scheduling:
- Rate-monotonic scheduling (static priorities)
- Earliest deadline first (dynamic)
OSPF (Open Shortest Path First) :
- Dijkstra's algorithm
- Link state advertisements
- Area hierarchy for scalability
BGP (Border Gateway Protocol) :
- Path vector protocol
- Policy-based routing
- Convergence challenges
| Function | Growth Rate | Example |
|---|---|---|
| Θ(1) | Constant | Array access |
| Θ(log n) | Logarithmic | Binary search |
| Θ(√n) | Square root | Sieve of Eratosthenes |
| Θ(n) | Linear | Linear search |
| Θ(n log n) | Linearithmic | Merge sort |
| Θ(n²) | Quadratic | Bubble sort |
| Θ(n³) | Cubic | Matrix multiplication |
| Θ(2ⁿ) | Exponential | Subset generation |
| Θ(n!) | Factorial | Permutations |
- P: Polynomial time
- NP: Nondeterministic polynomial time
- NP-complete: Hardest problems in NP
- NP-hard: At least as hard as NP-complete
- co-NP: Complements of NP problems
- PSPACE: Polynomial space
- EXPTIME: Exponential time
- Two pointers: Array traversal from both ends
- Sliding window: Subarray problems
- Binary search on answer: Optimization with monotonic property
- BFS/DFS: Graph exploration
- Topological sort: Dependency resolution
- Union-Find: Dynamic connectivity
- Trie: String prefix operations
- Segment tree: Range queries
- Dynamic programming: Optimal substructure
- Greedy: Local optimal choices
- Array: Two sum, merge intervals, product except self
- String: Palindromes, anagrams, pattern matching
- Linked list: Reverse, detect cycle, merge
- Tree: Traversals, LCA, path sum
- Graph: Clone graph, course schedule, word ladder
- Dynamic programming: Climbing stairs, coin change, edit distance
- Backtracking: Permutations, combinations, subsets
- Fast I/O: Use BufferedReader/BufferedWriter
- STL equivalents: Arrays.sort, Collections.sort
- Common libraries: java.util.*, algorithm in C++
- Debugging: Print intermediate values, use assertions
- Optimization: Precomputation, bit manipulation
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D.E. (1997). The Art of Computer Programming (Vols. 1-3). Addison-Wesley.
- Sedgewick, R., Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
- Kleinberg, J., Tardos, É. (2006). Algorithm Design. Addison-Wesley.
- Skiena, S.S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
- Dasgupta, S., Papadimitriou, C.H., Vazirani, U.V. (2006). Algorithms. McGraw-Hill.
- Aho, A.V., Hopcroft, J.E., Ullman, J.D. (1983). Data Structures and Algorithms. Addison-Wesley.
- Tarjan, R.E. (1983). Data Structures and Network Algorithms. SIAM.