Algorithms

related-skills: abl-v10-learning, abl-v12-learning

Skill: programming-algorithms

Programming Algorithms: A Comprehensive Guide for Algorithm Selection

Role: Senior Algorithm Engineer — select, implement, and optimize algorithms for problem-solving across domains.

Philosophy: Algorithmic Precision — choose the right tool for the job based on time/space trade-offs, input characteristics, and problem constraints. No fabrication — leverage established, proven algorithms.

Purpose: Why Standard Algorithms

The Problem with Fabrication:

• Reinventing algorithms introduces bugs and suboptimal solutions
• Standard algorithms have decades of academic analysis and optimization
• Edge cases are already understood and handled
• Performance characteristics are well-documented

When to Use Standard Algorithms:

1. Problem matches a known pattern (sorting, shortest path, etc.)
2. Input size suggests complexity constraints
3. Resource limits (time/space) are known
4. Industry standards exist for the domain

Key Principles:

• Trade-offs are inevitable: Time vs space, simplicity vs performance
• Context matters: Input size, distribution, and constraints dictate choices
• Proof first, optimize later: Ensure correctness before micro-optimizations

related-skills: abl-v10-learning, abl-v12-learning

Table of Contents

1. Sorting Algorithms
2. Searching Algorithms
3. Graph Algorithms
4. Dynamic Programming
5. Greedy Algorithms
6. String Algorithms
7. Mathematical Algorithms
8. Geometric Algorithms
9. Backtracking Algorithms
10. Numerical Algorithms
11. Probabilistic Algorithms
12. Streaming Algorithms
13. Algorithm Selection Guide

related-skills: abl-v10-learning, abl-v12-learning

Sorting Algorithms

Quick Sort

• Alternative Names: Partition-exchange sort
• Time Complexity:
  • Best: O(n log n) (balanced partitions)
  • Average: O(n log n)
  • Worst: O(n²) (poor pivot selection)
• Space Complexity: O(log n) (recursion stack)
• Key Use Cases:
  • General-purpose sorting when cache locality matters
  • In-place sorting with minimal memory overhead
  • Average-case optimal for random data
• When to Choose:
  • Data is randomly distributed
  • Memory is constrained (in-place)
  • Average performance matters more than worst-case guarantee
  • Not suitable for linked lists or nearly-sorted data
• Optimizations:
  • Use median-of-three pivot selection
  • Switch to insertion sort for small partitions (n < 10-20)
  • Iterative implementation to avoid stack overflow

Merge Sort

• Alternative Names: Mergesort
• Time Complexity:
  • Best: O(n log n)
  • Average: O(n log n)
  • Worst: O(n log n)
• Space Complexity: O(n) (temporary arrays)
• Key Use Cases:
  • Linked list sorting
  • External sorting (files too large for memory)
  • Stable sorting required
  • Parallel processing (tasks are independent)
• When to Choose:
  • Stability is required (equal elements maintain order)
  • Sorting linked lists (O(1) extra space)
  • External sorting with disk I/O
  • Predictable performance needed
• Optimizations:
  • Bottom-up (iterative) implementation
  • Use insertion sort for small subarrays
  • Parallel merge sort for multi-core systems

Heap Sort

• Alternative Names: Heap sorting
• Time Complexity:
  • Best: O(n log n)
  • Average: O(n log n)
  • Worst: O(n log n)
• Space Complexity: O(1) (in-place)
• Key Use Cases:
  • In-place sorting with guaranteed O(n log n) performance
  • Priority queue implementation
  • Finding top-k elements (use min-heap of size k)
  • Memory-constrained environments
• When to Choose:
  • Worst-case performance guarantee needed
  • Memory is extremely constrained
  • Building priority queues
  • Not suitable for nearly-sorted data (no early exit)
• Optimizations:
  • Build heap in O(n) time (Floyd's algorithm)
  • Use binary heap for arrays, binomial heap for decreases

Radix Sort

• Alternative Names: Bucket sort (for integers), LSD radix sort
• Time Complexity:
  • Best: O(nk)
  • Average: O(nk)
  • Worst: O(nk)
  • Where k = number of digits/characters
• Space Complexity: O(n + k) (buckets)
• Key Use Cases:
  • Sorting integers with fixed width
  • Sorting strings by characters
  • Stable sorting for digit-by-digit processing
  • When k is small relative to n
• When to Choose:
  • Integers with bounded range
  • Strings with fixed maximum length
  • Need stable sorting
  • k is O(1) or very small
  • Not suitable for floating-point or large k values
• Optimizations:
  • MSD (Most Significant Digit) for string sorting
  • LSD (Least Significant Digit) for fixed-width integers
  • Use counting sort as stable subroutine

Bucket Sort

• Alternative Names: Bin sort
• Time Complexity:
  • Best: O(n + k) (uniform distribution)
  • Average: O(n + k)
  • Worst: O(n²) (all elements in one bucket)
• Space Complexity: O(nk) (buckets)
• Key Use Cases:
  • Uniformly distributed floating-point numbers
  • Sorting data that can be partitioned into ranges
  • Database partitioning
  • Parallel processing (independent buckets)
• When to Choose:
  • Input is uniformly distributed over a range
  • Can create appropriate number of buckets
  • Parallel sorting allowed
  • Not suitable for skewed distributions

Insertion Sort

• Time Complexity:
  • Best: O(n) (already sorted)
  • Average: O(n²)
  • Worst: O(n²)
• Space Complexity: O(1) (in-place)
• Key Use Cases:
  • Nearly-sorted data
  • Small datasets (n < 20)
  • Online algorithms (inserting elements one at a time)
  • Subroutine for hybrid algorithms
• When to Choose:
  • Small input sizes (often used as base case)
  • Data is already partially sorted
  • Online sorting (streaming input)
  • Minimal memory overhead required

Bubble Sort

• Time Complexity:
  • Best: O(n) (optimized with swapped flag)
  • Average: O(n²)
  • Worst: O(n²)
• Space Complexity: O(1) (in-place)
• Key Use Cases:
  • Educational demonstrations
  • Detecting nearly-sorted data
  • Small datasets with few swaps needed
• When to Choose:
  • Almost never for production (except teaching)
  • Detect if data is already sorted (O(n))
  • Very small datasets where simplicity matters

Selection Sort

• Time Complexity:
  • Best: O(n²)
  • Average: O(n²)
  • Worst: O(n²)
• Space Complexity: O(1) (in-place)
• Key Use Cases:
  • Minimizing number of swaps
  • Small datasets where swaps are expensive
  • Educational demonstrations
• When to Choose:
  • Memory writes are costly (minimize to n swaps)
  • Small datasets
  • Never for large datasets

Shell Sort

• Alternative Names: Shell's method
• Time Complexity:
  • Best: O(n log² n)
  • Average: O(n log² n) to O(n^(3/2))
  • Worst: O(n²)
• Space Complexity: O(1) (in-place)
• Key Use Cases:
  • Middle ground between O(n²) and O(n log n)
  • When quick sort/merge sort are too complex
  • Embedded systems with limited resources
• When to Choose:
  • Need better than O(n²) without complexity of O(n log n)
  • Memory-constrained but need better performance

related-skills: abl-v10-learning, abl-v12-learning

Searching Algorithms

Binary Search

• Alternative Names: Half-interval search, logarithmic search
• Time Complexity:
  • Best: O(1)
  • Average: O(log n)
  • Worst: O(log n)
• Space Complexity: O(1) iterative, O(log n) recursive
• Key Use Cases:
  • Finding elements in sorted arrays
  • Finding first/last occurrence
  • Finding minimum/maximum in bitonic/unimodal functions
  • Floating-point binary search (precision search)
• When to Choose:
  • Data is sorted or can be sorted
  • Need O(log n) lookup time
  • Static data (not frequently updated)
  • Not suitable for unsorted or frequently changing data
• Variants:
  • Lower bound / Upper bound (first ≥ / first >)
  • Rotated array search
  • 2D matrix search (row-wise and column-wise sorted)
  • Real number binary search (for precision)

Interpolation Search

• Time Complexity:
  • Best: O(log log n) (uniform distribution)
  • Average: O(log log n)
  • Worst: O(n) (non-uniform distribution)
• Space Complexity: O(1)
• Key Use Cases:
  • Uniformly distributed sorted data
  • Large datasets with known distribution
  • Numeric data with continuous values
• When to Choose:
  • Data is uniformly distributed
  • Data is sorted and large
  • Not suitable for sparse or non-uniform data

Exponential Search

• Alternative Names: Galloping search, doubling search
• Time Complexity:
  • Best: O(1)
  • Average: O(log i)
  • Worst: O(log i)
  • Where i is the position of the element
• Space Complexity: O(1)
• Key Use Cases:
  • Unbounded/infinite sorted arrays
  • Finding element position for binary search
  • When element might be near the beginning
• When to Choose:
  • Sorted array but size unknown
  • Element likely near start
  • As preprocessing for binary search

Linear Search

• Time Complexity:
  • Best: O(1)
  • Average: O(n)
  • Worst: O(n)
• Space Complexity: O(1)
• Key Use Cases:
  • Unsorted data
  • Small datasets
  • Single search (sorting not worth it)
  • Linked lists
• When to Choose:
  • Data is unsorted
  • Small n where O(n) is acceptable
  • Single search on large dataset

Ternary Search

• Time Complexity:
  • Best: O(1)
  • Average: O(log n)
  • Worst: O(log n)
• Space Complexity: O(1)
• Key Use Cases:
  • Finding minimum/maximum of unimodal function
  • Convex/concave functions
  • Golden section search alternative
• When to Choose:
  • Optimization of unimodal functions
  • When binary search doesn't apply
  • Compare with golden section search

Jump Search

• Alternative Names: Block search
• Time Complexity:
  • Best: O(1)
  • Average: O(√n)
  • Worst: O(√n)
• Space Complexity: O(1)
• Key Use Cases:
  • Sorted data where jumping back is expensive
  • Large datasets on disk
  • Intermediate between linear and binary search
• When to Choose:
  • Jumping back is costly (disk seeks)
  • O(√n) is acceptable

related-skills: abl-v10-learning, abl-v12-learning

Graph Algorithms

Breadth-First Search (BFS)

• Time Complexity: O(V + E)
• Space Complexity: O(V) (queue)
• Key Use Cases:
  • Shortest path in unweighted graphs
  • Level-order traversal
  • Connected components
  • Bipartite checking
  • Web crawling
• When to Choose:
  • Unweighted shortest path
  • Need all nodes at distance k
  • Flow networks (Ford-Fulkerson)
  • Social network analysis

Depth-First Search (DFS)

• Time Complexity: O(V + E)
• Space Complexity: O(V) (recursion stack)
• Key Use Cases:
  • Topological sorting
  • Cycle detection
  • Strongly connected components
  • Maze solving
  • Path finding
• When to Choose:
  • Need to explore all paths
  • Stack-based iteration
  • Topological sort
  • Tarjan's SCC algorithm
• Variants:
  • Iterative DFS (explicit stack)
  • DFS with parent tracking
  • DFS forest (multiple components)

Dijkstra's Algorithm

• Alternative Names: Dijkstra's shortest path
• Time Complexity:
  • O(V²) (naive)
  • O((V + E) log V) (with priority queue)
  • O(V log V + E) (Fibonacci heap)
• Space Complexity: O(V)
• Key Use Cases:
  • Single-source shortest path (non-negative weights)
  • Routing protocols
  • GPS navigation
  • Network optimization
• When to Choose:
  • Non-negative edge weights
  • Single source to all destinations
  • Need exact shortest path
  • Not suitable for negative weights
• Optimizations:
  • Use Fibonacci heap for O(V log V + E)
  • Early termination when target reached
  • Bidirectional Dijkstra for source-target

Bellman-Ford Algorithm

• Time Complexity: O(VE)
• Space Complexity: O(V)
• Key Use Cases:
  • Single-source shortest path with negative weights
  • Negative cycle detection
  • Distributed routing
  • Linear programming
• When to Choose:
  • Graph may have negative edge weights
  • Need negative cycle detection
  • Distributed systems
  • Not suitable for dense graphs (too slow)

Floyd-Warshall Algorithm

• Alternative Names: Floyd's algorithm, Roy-Warshall
• Time Complexity: O(V³)
• Space Complexity: O(V²)
• Key Use Cases:
  • All-pairs shortest path
  • Transitive closure
  • Negative cycle detection
  • Density graphs
• When to Choose:
  • Need all-pairs shortest paths
  • Graph is dense (V³ acceptable)
  • Small V (V < 200-500)
  • Transitive closure needed
• Optimizations:
  • Use only when V is small
  • Can detect negative cycles

Kruskal's Algorithm

• Alternative Names: Minimum spanning tree (Kruskal)
• Time Complexity: O(E log E) or O(E log V)
• Space Complexity: O(V) (disjoint set)
• Key Use Cases:
  • Minimum spanning tree
  • Network design
  • Approximation algorithms
  • Clustering
• When to Choose:
  • Sparse graphs
  • Need MST
  • Edge-based processing
  • Disjoint set data structure available
• Optimizations:
  • Union by rank + path compression
  • Pre-sort edges

Prim's Algorithm

• Time Complexity:
  • O(V²) (naive)
  • O((V + E) log V) (priority queue)
  • O(E + V log V) (Fibonacci heap)
• Space Complexity: O(V)
• Key Use Cases:
  • Minimum spanning tree
  • Dense graphs
  • Network design
  • Image segmentation
• When to Choose:
  • Dense graphs (more edges)
  • Need MST
  • Vertex-based processing
  • Adjacency matrix available
• Comparison with Kruskal:
  • Kruskal better for sparse
  • Prim better for dense

Topological Sort

• Time Complexity: O(V + E)
• Space Complexity: O(V)
• Key Use Cases:
  • Dependency resolution
  • Course scheduling
  • Build systems
  • Job scheduling
• When to Choose:
  • Directed acyclic graph (DAG)
  • Need linear ordering
  • Dependency ordering required
  • Cycle detection (if not DAG)
• Methods:
  • DFS-based (post-order)
  • Kahn's algorithm (BFS with in-degrees)

A* Search Algorithm

• Time Complexity: O(b^d) worst case (where b = branching, d = depth)
• Space Complexity: O(b^d)
• Key Use Cases:
  • Heuristic path finding
  • Game AI
  • Robotics
  • Puzzle solving
• When to Choose:
  • Need shortest path with heuristic
  • Admissible heuristic available
  • Want to reduce search space
  • Not suitable without good heuristic
• Heuristic Requirements:
  • Admissible (never overestimates)
  • Consistent (triangle inequality)
• Variants: -IDA* (Iterative Deepening A*)
  • SMA* (Simplified Memory-Bounded A*)

Tarjan's SCC Algorithm

• Time Complexity: O(V + E)
• Space Complexity: O(V)
• Key Use Cases:
  • Strongly connected components
  • Graph condensation
  • Dependency analysis
  • Circuit simulation
• When to Choose:
  • Find SCCs in directed graph
  • Graph condensation needed
  • Cycle analysis
  • Topological sort on SCCs

Johnson's Algorithm

• Time Complexity: O(V² log V + VE)
• Space Complexity: O(V²)
• Key Use Cases:
  • All-pairs shortest path (sparse graphs)
  • Graphs with negative weights
• When to Choose:
  • Sparse graphs, all-pairs shortest path
  • Negative weights allowed
  • Better than Floyd-Warshall for sparse

Chinese Postman Problem

• Time Complexity: O(V² log V + E) for undirected
• Space Complexity: O(V²)
• Key Use Cases:
  • Route optimization (mail carrier)
  • Circuit board inspection
  • Street cleaning
• When to Choose:
  • Need to traverse all edges
  • Minimize total distance
  • Graph may have odd-degree vertices

Traveling Salesman Problem (Approximations)

• Time Complexity: Varies by heuristic
• Space Complexity: O(V²)
• Key Use Cases:
  • Route optimization
  • Logistics
  • Manufacturing (drill positioning)
• Heuristics:
  • Nearest neighbor: O(V²)
  • Christofides: O(V³) (3/2 approximation)
  • Simulated annealing
  • Genetic algorithms
• When to Choose:
  • NP-hard problem, need approximation
  • Real-world constraints
  • Exact solution not required

Minimum Cut (Stoer-Wagner)

• Time Complexity: O(V³) or O(VE + V² log V)
• Space Complexity: O(V²)
• Key Use Cases:
  • Network reliability
  • Image segmentation
  • Clustering
• When to Choose:
  • Find minimum edge cut
  • Graph partitioning
  • No source-sink constraint

Maximum Flow (Ford-Fulkerson)

• Time Complexity: O(E * max_flow) (integer capacities)
• Space Complexity: O(V + E)
• Key Use Cases:
  • Network flow
  • Bipartite matching
  • Image segmentation
  • transportation problems
• When to Choose:
  • Flow network optimization
  • Matching problems
  • Integer capacities
• Variants:
  • Edmonds-Karp: O(VE²) (BFS)
  • Dinic's: O(V²E) (level graph)
  • Push-relabel: O(V²E) (more efficient in practice)

Hopcroft-Karp Algorithm

• Time Complexity: O(E * √V)
• Space Complexity: O(V)
• Key Use Cases:
  • Maximum bipartite matching
  • Assignment problems
  • Job scheduling
• When to Choose:
  • Bipartite graph matching
  • Better than Ford-Fulkerson for bipartite
  • Sparse graphs

Max-Flow Min-Cut Theorem Applications

• Time Complexity: Same as underlying max-flow algorithm
• Key Use Cases:
  • Image segmentation (graph cuts)
  • Computer vision
  • Parallel computing
  • VLSI design

related-skills: abl-v10-learning, abl-v12-learning

Dynamic Programming

0/1 Knapsack Problem

• Time Complexity: O(nW) where W = capacity
• Space Complexity: O(nW) or O(W) (optimized)
• Key Use Cases:
  • Resource allocation
  • Investment portfolio
  • Container packing
  • Knapsack variations
• When to Choose:
  • Items can only be taken once
  • Capacity constraint
  • Optimal substructure exists
• Variants:
  • Unbounded knapsack (unlimited items)
  • Bounded knapsack (limited quantities)
  • Multiple knapsack
  • Fractional knapsack (greedy, not DP)
• Optimizations:
  • Space optimization (1D array)
  • Pruning based on bounds
  • Meet-in-the-middle for large n

Longest Common Subsequence (LCS)

• Time Complexity: O(mn) where m, n = string lengths
• Space Complexity: O(mn) or O(min(m, n))
• Key Use Cases:
  • Diff utilities
  • Bioinformatics (DNA matching)
  • Version control
  • Plagiarism detection
• When to Choose:
  • Two sequences common subsequence
  • Order matters, continuity not required
  • Not suitable for substring (use KMP/Rabin-Karp)
• Reconstruction:
  • Track decisions during DP
  • Backtrack to build actual LCS
• Optimizations:
  • Hirschberg's algorithm: O(min(m,n)) space
  • Early termination if no match

Longest Increasing Subsequence (LIS)

• Time Complexity: O(n²) (DP) or O(n log n) (patience sorting)
• Space Complexity: O(n)
• Key Use Cases:
  • Pattern recognition
  • Stock market analysis
  • Bioinformatics
  • Data smoothing
• When to Choose:
  • Strictly increasing (or non-decreasing)
  • Need longest monotonic subsequence
• O(n log n) Method:
  • Maintain active lists
  • Binary search for insertion
  • Track predecessors for reconstruction
• Variants:
  • Longest decreasing subsequence
  • Bitonic subsequence
  • Circular variant

Matrix Chain Multiplication

• Time Complexity: O(n³)
• Space Complexity: O(n²)
• Key Use Cases:
  • Optimal parenthesization
  • Compiler optimization
  • Dynamic programming example
• When to Choose:
  • Matrix multiplication order
  • Minimize scalar multiplications
  • All matrices compatible
• Optimizations:
  • Store optimal split points
  • Reconstruction for actual multiplication order

Edit Distance (Levenshtein)

• Time Complexity: O(mn)
• Space Complexity: O(mn) or O(min(m,n))
• Key Use Cases:
  • Spell checking
  • DNA sequence alignment
  • Fuzzy string matching
  • Version control
• When to Choose:
  • Minimum edits to transform string A to B
  • Insert, delete, replace operations
• Variants:
  • Hamming distance (same length, replace only)
  • Damerau-Levenshtein (adjacent swap)
  • Wagner-Fischer (generalization)
• Optimizations:
  • Space optimization
  • Early termination for small distances

Coin Change Problem

• Time Complexity: O(n * amount) where n = coin types
• Space Complexity: O(amount)
• Key Use Cases:
  • Making change (min coins)
  • Combinatorial counting
  • Resource allocation
• When to Choose:
  • Minimize number of coins
  • Count ways to make amount
  • DP applies (optimal substructure)
• Variants:
  • Minimum coins (0/1 or unlimited)
  • Count combinations
  • With limited coins
  • Greedy doesn't always work

Subset Sum Problem

• Time Complexity: O(n * sum) or O(n * 2^(n/2)) (meet-in-middle)
• Space Complexity: O(n * sum)
• Key Use Cases:
  • Scheduling
  • Resource allocation
  • Cryptography
  • NP-complete problems
• When to Choose:
  • Find subset with given sum
  • Decision problem (existential)
  • Optimization variant exists
• Optimizations:
  • Meet-in-the-middle for large n
  • Bitset optimization
  • Pseudo-polynomial DP

Traveling Salesman Problem (Dynamic Programming)

• Time Complexity: O(n² * 2^n)
• Space Complexity: O(n * 2^n)
• Key Use Cases:
  • Exact TSP for small n
  • Algorithm comparison
  • Benchmarking
• When to Choose:
  • n < 20-25
  • Need exact solution
  • Not suitable for large n
• Held-Karp Algorithm:
  • DP with bitmask
  • Track visited set and last city

Partition Problem

• Time Complexity: O(n * sum)
• Space Complexity: O(sum)
• Key Use Cases:
  • Fair division
  • Load balancing
  • NP-complete problems
• When to Choose:
  • Split into equal-sum subsets
  • Decision variant
  • Optimization (minimize difference)

Longest Palindromic Subsequence

• Time Complexity: O(n²)
• Space Complexity: O(n²)
• Key Use Cases:
  • Palindrome analysis
  • Bioinformatics
  • String algorithms
• When to Choose:
  • Find longest palindromic subsequence
  • Not substring (LPS can skip chars)
• Variants:
  • Longest palindromic substring (manacher's O(n))
  • Minimum deletions to make palindrome

Word Break Problem

• Time Complexity: O(n²) with dictionary lookup
• Space Complexity: O(n)
• Key Use Cases:
  • Text segmentation
  • Dictionary matching
  • Natural language processing
• When to Choose:
  • Can string be segmented into dictionary words?
  • Count all possible segmentations
• Optimizations:
  • Trie for dictionary lookup
  • Memoization
  • Early termination

Wildcard Pattern Matching

• Time Complexity: O(mn)
• Space Complexity: O(mn) or O(min(m,n))
• Key Use Cases:
  • Regex matching
  • File pattern matching
  • Text processing
• When to Choose:
  • Pattern with ? and * wildcards
  • Match against text
• Variants:
  • Regex with character classes
  • Case sensitivity
  • Multiline support

Unique Paths

• Time Complexity: O(mn)
• Space Complexity: O(mn) or O(min(m,n))
• Key Use Cases:
  • Grid path counting
  • Combinatorics
  • Robot motion planning
• When to Choose:
  • Grid with obstacles
  • Count paths from top-left to bottom-right
  • Only right/down moves allowed
• Variants:
  • With obstacles (grid[i][j] = 1 blocked)
  • With costs (minimum cost path)
  • With forbidden cells

Egg Dropping Puzzle

• Time Complexity: O(n * k²) or O(n * log k)
• Space Complexity: O(nk)
• Key Use Cases:
  • Testing/quality assurance
  • Optimization under uncertainty
  • Decision theory
• When to Choose:
  • Minimize trials to find critical floor
  • k eggs, n floors
  • Binary search when 2 eggs

Catalan Numbers Applications

• Time Complexity: O(n²) for DP, O(n) for formula
• Space Complexity: O(n)
• Key Use Cases:
  • Parentheses matching
  • Binary tree counting
  • Polygon triangulation
  • Dyck paths
• When to Choose:
  • Problems with Catalan structure
  • Combinatorial counting
  • Recursive structure
• Applications:
  • n pairs of valid parentheses
  • n+1 leaves in full binary tree
  • n×n grid monotonic paths
  • Convex polygon triangulation

Optimal Binary Search Tree

• Time Complexity: O(n³)
• Space Complexity: O(n²)
• Key Use Cases:
  • Compiler design
  • Database indexing
  • Optimal search structure
• When to Choose:
  • Given probabilities, build optimal BST
  • Minimize search cost
  • Static search set
• Optimizations:
  • Knuth's optimization (if quadrangle inequality)
  • O(n²) with Knuth optimization

Bitmask DP Applications

• Time Complexity: O(n * 2^n) or O(m * 3^(n/2))
• Space Complexity: O(2^n)
• Key Use Cases:
  • Subset problems
  • Graph problems (TSP, Hamiltonian)
  • Set cover
• When to Choose:
  • n < 20-25
  • Subsets or states can be encoded as bitmask
  • State space is 2^n

DP on Trees

• Time Complexity: O(V) for simple, O(V * k²) for k-state
• Space Complexity: O(V)
• Key Use Cases:
  • Tree diameter
  • Tree center
  • Tree coloring
  • Tree independence
• When to Choose:
  • Tree structure
  • Root the tree arbitrarily
  • Combine children's results
• Common Patterns:
  • Tree diameter (two DFS)
  • Tree center (eccentricity)
  • Tree isomorphism
  • Tree knapsack

DP with Bitwise Operations

• Time Complexity: Varies
• Space Complexity: Varies
• Key Use Cases:
  • Subset XOR sums
  • Bit manipulation problems
  • State compression
• When to Choose:
  • Bitwise operations on subsets
  • XOR-based problems
  • Bitmask DP

related-skills: abl-v10-learning, abl-v12-learning

Greedy Algorithms

Activity Selection Problem

• Time Complexity: O(n log n) (sorting) or O(n) (if sorted)
• Space Complexity: O(1) extra
• Key Use Cases:
  • Scheduling resources
  • Meeting room allocation
  • Single-resource scheduling
• When to Choose:
  • Select maximum non-overlapping activities
  • Greedy choice works (earliest finish time)
  • Not for weighted activities (need DP)

Huffman Coding

• Time Complexity: O(n log n) (priority queue)
• Space Complexity: O(n)
• Key Use Cases:
  • Data compression
  • Prefix codes
  • Optimal binary encoding
• When to Choose:
  • Character frequencies known
  • Minimal expected codeword length
  • Prefix-free encoding needed
• Algorithm:
  • Build frequency table
  • Create min-heap of nodes
  • Combine two smallest frequencies
  • Build tree and assign codes

Kruskal's MST (Greedy)

• Time Complexity: O(E log E)
• Space Complexity: O(V)
• Key Use Cases:
  • Minimum spanning tree
  • Network design
  • Clustering
• When to Choose:
  • Sparse graphs
  • Edge-based processing
  • Union-find available

Prim's MST (Greedy)

• Time Complexity: O(V²) or O(E log V)
• Space Complexity: O(V)
• Key Use Cases:
  • Minimum spanning tree
  • Dense graphs
  • Vertex-based processing
• When to Choose:
  • Dense graphs
  • Adjacency matrix
  • Vertex expansion

Dijkstra's Algorithm (Greedy)

• Time Complexity: O((V + E) log V)
• Space Complexity: O(V)
• Key Use Cases:
  • Shortest path (non-negative)
  • Routing
  • Network optimization
• When to Choose:
  • Non-negative edge weights
  • Single source
  • Greedy choice (shortest known distance)

Fractional Knapsack

• Time Complexity: O(n log n) (sorting)
• Space Complexity: O(1) extra
• Key Use Cases:
  • Resource allocation
  • Maximizing value with weight limit
  • Continuous items
• When to Choose:
  • Items can be split
  • Value/weight ratio matters
  • Not 0/1 knapsack (needs DP)

Job Sequencing with Deadlines

• Time Complexity: O(n²) or O(n log n) with union-find
• Space Complexity: O(n)
• Key Use Cases:
  • Job scheduling
  • Profit maximization
  • Deadline constraints
• When to Choose:
  • Jobs with deadlines and profits
  • One unit time per job
  • Maximize total profit

Coin Change (Greedy)

• Time Complexity: O(n) where n = number of coins
• Space Complexity: O(1)
• Key Use Cases:
  • Standard currency systems
  • USD, EUR coin systems
  • Greedy-valid denominations
• When to Choose:
  • Greedy-valid currency (US, EUR)
  • Not for arbitrary denominations
  • Check if greedy works first

Graph Coloring (Greedy)

• Time Complexity: O(V + E)
• Space Complexity: O(V)
• Key Use Cases:
  • Register allocation
  • Scheduling
  • Map coloring
• When to Choose:
  • Approximation needed
  • Order matters
  • Not optimal but fast

Stable Marriage Problem (Gale-Shapley)

• Time Complexity: O(n²)
• Space Complexity: O(n²)
• Key Use Cases:
  • Hospital-resident matching
  • School choice
  • Two-sided matching
• When to Choose:
  • Two sets with preferences
  • Stable matching required
  • Men-optimal/women-optimal

Minimum Spanning Tree (General)

• Time Complexity: O(E log V)
• Space Complexity: O(V)
• Key Use Cases:
  • Network design
  • Approximation algorithms
  • Clustering
• When to Choose:
  • Connected, undirected graph
  • Minimum total edge weight
  • Greedy algorithms work

Job Scheduler (Shortest Job First)

• Time Complexity: O(n log n) (priority queue)
• Space Complexity: O(n)
• Key Use Cases:
  • Process scheduling
  • Batch processing
  • Minimize average wait time
• When to Choose:
  • Process burst times known
  • Minimize average waiting time
  • Non-preemptive or preemptive

Interval Scheduling (Weighted)

• Time Complexity: O(n log n) with binary search
• Space Complexity: O(n)
• Key Use Cases:
  • Resource allocation with weights
  • Profit maximization
  • Job selection
• When to Choose:
  • Weighted activities
  • Non-overlapping subset
  • Greedy doesn't work, use DP

related-skills: abl-v10-learning, abl-v12-learning

String Algorithms

KMP (Knuth-Morris-Pratt)

• Time Complexity: O(n + m) where n = text, m = pattern
• Space Complexity: O(m) (LPS array)
• Key Use Cases:
  • Pattern matching
  • DNA sequence search
  • Text editors
  • Security scanning
• When to Choose:
  • Multiple pattern occurrences
  • Pattern has repetitions
  • Need linear time guarantee
  • Preprocessing pattern allowed
• LPS Array:
  • Longest proper prefix which is also suffix
  • Avoids re-comparing characters

Rabin-Karp

• Time Complexity: O(n + m) average, O(nm) worst
• Space Complexity: O(1) (constant operations)
• Key Use Cases:
  • Plagiarism detection
  • Multi-pattern matching
  • String hashing
  • Duplicate detection
• When to Choose:
  • Multiple patterns to search
  • Rolling hash useful
  • Average case acceptable
  • Hash collisions manageable

Boyer-Moore

• Time Complexity: O(n/m * m!) worst, O(n/m) average
• Space Complexity: O(σ) where σ = alphabet size
• Key Use Cases:
  • Large alphabet (ASCII, Unicode)
  • Large text, small pattern
  • Text editors (grep)
  • Bioinformatics
• When to Choose:
  • Large alphabet (letters, not just ACGT)
  • Pattern near end of text
  • Good heuristic behavior
  • Not for small alphabet

Z-Algorithm

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)
• Key Use Cases:
  • Pattern matching
  • String prefix matching
  • String repetition detection
  • Concatenation problems
• When to Choose:
  • Z-array computation
  • Prefix matching
  • Alternative to KMP
  • Suffix matching with sentinel

Manacher's Algorithm

• Time Complexity: O(n)
• Space Complexity: O(n)
• Key Use Cases:
  • Longest palindromic substring
  • All palindromes in string
  • Palindrome density
• When to Choose:
  • Linear time palindrome -Substring (not subsequence)
  • All palindromes needed
• Key Insight:
  • Uses symmetry to avoid re-computation
  • Expands around centers with memoization

Suffix Array

• Time Complexity: O(n log n) (sort) or O(n) (SAIS)
• Space Complexity: O(n)
• Key Use Cases:
  • Pattern matching (with binary search)
  • Burrows-Wheeler transform
  • Data compression
  • Genomics
• When to Choose:
  • Multiple queries on same text
  • Memory efficiency
  • LCP array for additional queries
  • Alternative to suffix tree
• Construction:
  • Sorting all suffixes
  • Radix sort for O(n)
  • DC3 algorithm for O(n)

Suffix Tree (Ukkonen's)

• Time Complexity: O(n)
• Space Complexity: O(n)
• Key Use Cases:
  • Fast pattern matching
  • Longest repeated substring
  • Substring queries
  • Bioinformatics
• When to Choose:
  • Single query, fast lookup
  • Multiple pattern queries
  • Space permits
  • Complex query support
• Applications:
  • Longest repeated substring
  • Longest common substring
  • Palindrome detection

Rolling Hash (Rabin-Karp)

• Time Complexity: O(1) per shift
• Space Complexity: O(1)
• Key Use Cases:
  • Rabin-Karp
  • String matching
  • Duplicate detection
  • Streaming
• When to Choose:
  • Multiple substring hashes needed
  • Window sliding
  • Hash collision handling

Longest Prefix Suffix (LPS) / Failure Function

• Time Complexity: O(m)
• Space Complexity: O(m)
• Key Use Cases:
  • KMP algorithm
  • String border
  • Periodicity detection
• When to Choose:
  • KMP preprocessing
  • String borders
  • Pattern analysis

Boyer-Moore-Horspool

• Time Complexity: O(n) average
• Space Complexity: O(σ)
• Key Use Cases:
  • Simplified Boyer-Moore
  • Text search
  • Binary files
• When to Choose:
  • Simpler than Boyer-Moore
  • Good average performance
  • Fixed alphabet

Apostolico-Giancarlo

• Time Complexity: O(n) average
• Space Complexity: O(m)
• Key Use Cases:
  • Speeding up KMP
  • Avoiding re-comparisons
  • Pattern matching
• When to Choose:
  • KMP with early termination
  • Memory bandwidth limited
  • Large pattern

Multiple Pattern Matching (Aho-Corasick)

• Time Complexity: O(n + m + z) where z = matches
• Space Complexity: O(m * σ)
• Key Use Cases:
  • Multiple keywords
  • Security scanning
  • Text processing
  • intrusion detection
• When to Choose:
  • Multiple patterns (3+)
  • All occurrences needed
  • Linear time in text length
  • Dictionary matching
• Structure:
  • Trie with failure links
  • Output function

Suffix Trie

• Time Complexity: O(m) for query
• Space Complexity: O(m * σ^m) (exponential)
• Key Use Cases:
  • Educational
  • Small strings only
  • Pattern matching
• When to Choose:
  • Never for production
  • Only for small m
  • Understand suffix trees

Longest Repeated Substring

• Time Complexity: O(n) (suffix tree) or O(n log n) (suffix array)
• Space Complexity: O(n)
• Key Use Cases:
  • Plagiarism detection
  • DNA analysis
  • Code duplication
• When to Choose:
  • Repeat detection
  • Suffix tree/array available
  • Overlapping allowed or not

Longest Common Substring

• Time Complexity: O(n + m) (suffix tree) or O(nm) (DP)
• Space Complexity: O(n + m)
• Key Use Cases:
  • DNA comparison
  • File diff
  • Code similarity
• When to Choose:
  • Contiguous match
  • Suffix tree/array for linear
  • DP for simplicity
• DP Approach:
  • Table[i][j] = length of common substring ending at i, j
  • Maximum value is answer

Palindromic Tree (Eertree)

• Time Complexity: O(n)
• Space Complexity: O(n)
• Key Use Cases:
  • All palindromes in string
  • Palindrome counting
  • Palindromic density
• When to Choose:
  • All palindromes
  • Online algorithm
  • Memory efficient
• Structure:
  • Two roots (even/odd length)
  • Suffix links
  • Palindromic nodes

String Matching with Wildcards

• Time Complexity: O(mn)
• Space Complexity: O(mn)
• Key Use Cases:
  • Shell globbing
  • File matching
  • Query patterns
• When to Choose:
  • Pattern with ? and *
  • DP approach
  • Memoization for optimization

related-skills: abl-v10-learning, abl-v12-learning

Mathematical Algorithms

Euclidean GCD

• Time Complexity: O(log min(a, b))
• Space Complexity: O(1) iterative, O(log n) recursive
• Key Use Cases:
  • Simplifying fractions
  • LCM calculation
  • Cryptography
  • Number theory
• When to Choose:
  • Greatest common divisor
  • Euclidean algorithm
  • Binary GCD alternative for bit operations
• Extensions:
  • Extended GCD (Bezout coefficients)
  • Multiple number GCD
  • LCM = (a * b) / GCD(a, b)

Binary Exponentiation (Fast Power)

• Time Complexity: O(log n)
• Space Complexity: O(log n) recursive, O(1) iterative
• Key Use Cases:
  • Power computation
  • Matrix exponentiation
  • Modular exponentiation
  • Fibonacci numbers
• When to Choose:
  • Large exponents
  • Modular arithmetic
  • Matrix powers
  • Exponentiation by squaring
• Variants:
  • Iterative implementation
  • Modular exponentiation (a^b mod m)
  • Matrix exponentiation
  • Fast Fibonacci (O(log n))

Sieve of Eratosthenes

• Time Complexity: O(n log log n)
• Space Complexity: O(n)
• Key Use Cases:
  • Prime generation
  • Primality testing
  • Number theory
  • Cryptography preprocessing
• When to Choose:
  • Generate primes up to n
  • Multiple primality tests
  • Sieve is better for batch
• Optimizations:
  • Sieve of Atkin (O(n / log log n))
  • Segmented sieve (for large n)
  • Only odd numbers
  • Bitset compression

Extended Euclidean Algorithm

• Time Complexity: O(log min(a, b))
• Space Complexity: O(log n)
• Key Use Cases:
  • Modular inverse
  • Bezout coefficients
  • Chinese Remainder Theorem
  • RSA cryptography
• When to Choose:
  • Find x, y such that ax + by = GCD(a, b)
  • Modular inverse exists
  • Linear Diophantine equations

Miller-Rabin Primality Test

• Time Complexity: O(k * log³ n) where k = iterations
• Space Complexity: O(1)
• Key Use Cases:
  • Large number primality
  • Cryptography
  • Probabilistic testing
  • BigInteger libraries
• When to Choose:
  • Large numbers (100+ bits)
  • Probabilistic acceptable
  • Deterministic for 64-bit (specific bases)
• Deterministic:
  • For n < 2^64, specific bases guarantee correctness
  • Common bases: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Lucas-Lehmer Primality Test

• Time Complexity: O(log² p) for Mersenne number M_p
• Space Complexity: O(log p)
• Key Use Cases:
  • Mersenne primes
  • Large prime discovery
  • GIMPS
• When to Choose:
  • Mersenne numbers (2^p - 1)
  • specifically for Mersenne primes
  • Deterministic for Mersenne

Modular Arithmetic

• Key Operations:
  • Addition: (a + b) mod m
  • Multiplication: (a * b) mod m
  • Division: a * mod_inverse(b, m) mod m
  • Subtraction: (a - b + m) mod m
• When to Choose:
  • Avoid overflow
  • Cryptography
  • Large number arithmetic

Fast Fourier Transform (FFT)

• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Key Use Cases:
  • Polynomial multiplication
  • Signal processing
  • Large integer multiplication
  • Convolution
• When to Choose:
  • Polynomial multiplication
  • Convolution theorem
  • Signal analysis
  • Circular convolution

Karatsuba Multiplication

• Time Complexity: O(n^log₂3) ≈ O(n^1.585)
• Space Complexity: O(n)
• Key Use Cases:
  • Large integer multiplication

…(truncated)