# Algorithms

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

- Skill: `paulpas/algorithms` (Agent Skill)
- Install (CLI): `npx skillmds@latest add paulpas/algorithms`
- Raw SKILL.md: https://api.skillmd.com/api/skills/paulpas/algorithms/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: paulpas (https://skillmd.com/u/paulpas)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/paulpas/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](#sorting-algorithms)
2. [Searching Algorithms](#searching-algorithms)
3. [Graph Algorithms](#graph-algorithms)
4. [Dynamic Programming](#dynamic-programming)
5. [Greedy Algorithms](#greedy-algorithms)
6. [String Algorithms](#string-algorithms)
7. [Mathematical Algorithms](#mathematical-algorithms)
8. [Geometric Algorithms](#geometric-algorithms)
9. [Backtracking Algorithms](#backtracking-algorithms)
10. [Numerical Algorithms](#numerical-algorithms)
11. [Probabilistic Algorithms](#probabilistic-algorithms)
12. [Streaming Algorithms](#streaming-algorithms)
13. [Algorithm Selection Guide](#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)