Algorithms

From sorting to dynamic programming — step-by-step guides with interactive examples.

Complexity & Analysis

Big-O, Theta, Omega

How fast does your recipe slow down as the guest list grows?

Amortized Analysis

One big bill, paid in tiny installments

Recurrence Relations

A recipe that calls itself — until it's simple enough to solve

Sorting

Sorting a hand of cards — three ways, one speed

Split, sort each half, merge — guaranteed \(O(n \log n)\) every time

Pick a pivot, split the crowd — everyone shorter left, taller right

A tournament bracket where the champion always rises to the top

Linear-Time Sorting

Sort by mailbox number, not by comparing — break the \(O(n \log n)\) wall

Comparison Lower Bound

Why no comparison sort can ever beat \(O(n \log n)\) — a mathematical proof

Searching & Selection

Cut the problem in half — every single time

Binary Search on Answer

When you can't search the array — search the answer itself

Exponential & Interpolation Search

Find the range first, then binary search it

Find the kth smallest without fully sorting

Median of Medians

A guaranteed-good pivot — every single time

Divide & Conquer

Split the problem, solve the pieces, combine the results

Count Inversions

Measure how shuffled a sequence is — in \(O(n \log n)\)

Compute \(x^n\) in \(O(\log n)\) — not \(O(n)\) multiplications

Karatsuba Multiplication

3 multiplications instead of 4 — per recursive level

Closest Pair of Points

Find the two nearest cities on a map — without measuring every pair

Greedy Algorithms

Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't

Interval Scheduling

Book as many non-overlapping meetings as possible — always pick the one that ends earliest

Fractional Knapsack

Filling a backpack with gold dust — take the most valuable per gram first

Huffman Encoding

Give shorter Morse code to the letters you use most — save space on every message

Task Scheduling

Do homework by closest deadline first — miss nothing, earn the most

MST — Greedy Lens

Connect all towns with the least road — always add the cheapest road that doesn't create a loop

Dynamic Programming

Never solve the same puzzle piece twice — write it down and look it up next time

Memoization vs Tabulation

Top-down is calling a friend who calls a friend. Bottom-up is filling a spreadsheet row by row.

Build the answer one step at a time — just like climbing stairs

Pack a suitcase for maximum value — each item is all-or-nothing

Unbounded Knapsack

Take as many of each item as you want — the vending machine version

Longest Common Subsequence

Find the longest story two sequences share — skipping is allowed

Longest Increasing Subsequence

Find the longest staircase hidden inside a jumbled sequence

How many typo-fixes does it take to turn one word into another?

Matrix Chain Multiplication

The order you multiply matrices matters enormously — find the cheapest order

DP on Intervals

Solve tiny sections first, then merge them into bigger ones

Each node's answer depends on its children — compute bottom-up

Track every possible subset of choices in a single integer

Count numbers with digit constraints — without checking each one

Graph Algorithms

BFS & DFS Revisited

Two ways to explore a graph — level by level, or all the way in

Topological Sort

Order tasks by their dependencies — no chicken-before-egg

Dijkstra's Algorithm

Always extend the cheapest road first — GPS navigation for graphs

Bellman-Ford & SPFA

Handle negative weights and catch negative cycles

Find shortest paths between every pair of cities in one sweep

Smarter than Dijkstra — use a hint to head in the right direction

Tarjan's Algorithm

Find all tightly-knit groups in a directed graph in one pass

Kosaraju's Algorithm

Find mutual-follow groups with two clever graph walks

Eulerian Path & Circuit

Can you cross every bridge exactly once? Euler answered this in 1736

Hamiltonian Path

Visit every house exactly once — far harder than every bridge

Network Flow

Max Flow / Min Cut

How much water fits through your pipe network? The bottleneck decides

Ford-Fulkerson with BFS — guaranteed polynomial time, no infinite loops

Dinic's Algorithm

Batch all shortest augmenting paths in one go — dramatically faster than one at a time

Bipartite Matching

Match students to internships — find the maximum number of happy pairs

Hungarian Algorithm

Assign workers to tasks at the lowest possible total cost — the perfect match

String Algorithms

When searching for a word, never go backwards — use what you already know

Find a word in a book by its fingerprint — check character-by-character only when fingerprints match

Z-array: match length at every position — linear pattern matching

Read the pattern backwards, skip huge chunks — sublinear in practice

Suffix Array Construction

All suffixes sorted — \(O(m \log n)\) substring search

Find all patterns at once — one pass, \(O(n + matches)\)

Randomized Algorithms

Las Vegas vs Monte Carlo

Correct-always vs probably-correct — two flavors of randomized algorithms

Randomized Quick Sort

A random pivot destroys adversarial worst-case inputs

Reservoir Sampling

Sample k items fairly from a stream you see only once

Probabilistic BST alternative — \(O(\log n)\) expected

Probably yes, definitely no — a memory-sipping membership checker

Advanced Topics

Explore every path, retreat the moment you hit a dead end

Backtracking with a crystal ball — prune branches that can't possibly win

Approximation Algorithms

90% of the way there in 1% of the time — with a proof to back it up

NP, NP-Complete, NP-Hard

The million-dollar question: can finding an answer ever be as easy as checking one?

Bit Manipulation

Flip switches at the speed of electricity — and do it in \(O(1)\)

Answer a thousand range queries by sorting them cleverly — not answering them in order

Sqrt Decomposition

Split the array into √n chunks — too big to check every element, too small to need a fancy tree