Advanced

Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an `O(n)` operation. So why do textbooks still call append `O(1)`? Because amortized over a long sequence of appends, the rare expensive operation is paid for by many cheap ones. **Amortized Analysis** is the formal machinery that makes this kind of argument rigorous. This lesson teaches the three classical methods. The **aggregate method** sums the total cost of `n` operations and divides by `n` for a per-operation bound. The **accounting (banker's) method** charges each operation a fixed amount and stores credits on the data structure to pay for future expensive ones. The **potential (physicist's) method** defines a potential function `Phi` and computes amortized cost as actual cost plus the change in `Phi`. You will apply all three to dynamic array doubling, stacks with multipop, and binary counters, and see how amortized `O(1)` differs from worst-case `O(1)` and from average-case analysis. This lesson stands on the shoulders of **Big-O Notation (Upper Bound)** and **Time Complexity Analysis Techniques**. From those lessons you can already analyze a single operation; amortized analysis is what you reach for when the cost of *one* operation is misleading and the right object of study is a *sequence* of operations. Next you will move to **Recurrence Relations**, the other major analysis tool, used when an algorithm's cost is most naturally written recursively rather than as a running total.

Goldbach's conjecture has been verified for every even integer up to 4 * 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a hundred unit tests and still fail on the empty list or the input size your tests never reached. **Basic Proof Techniques** equips you with the small set of argument styles that turn intuition into certainty about correctness, complexity bounds, and data structure invariants. Direct proof chains definitions and prior facts to a claim. Proof by contradiction assumes the opposite and derives a logical impossibility, as in the irrationality of `sqrt(2)` and the `Omega(n log n)` lower bound for comparison sorts. Mathematical induction, in weak and strong forms, proves statements over the natural numbers via a base case and an inductive step, the backbone of recurrence solutions and loop invariants. Proof by contraposition swaps `P implies Q` for the equivalent `not Q implies not P`, and proof by cases breaks a claim into exhaustive subcases. This lesson builds on **Discrete Mathematics Basics**, where you met sets, propositional logic, implications, and the first taste of formal proof. Here those informal sketches become the disciplined patterns that algorithm analysis, theoretical CS, and clean engineering arguments all rely on. With proofs in hand, you have completed the foundations track and are ready to step into **Arrays & Strings** and the rest of the data structures curriculum, armed to analyze every operation rigorously.

Some problems have algorithms that finish in seconds on inputs of size a million. Others, like finding the shortest tour through 30 cities, can defeat the world's fastest computers no matter how cleverly you code. The boundary between these two worlds is studied formally in **complexity theory**, and the rough map of that boundary is given by **complexity classes**: `P`, `NP`, `NP-Complete`, and `NP-Hard`. This lesson introduces those classes conceptually. You will see how `P` collects problems solvable in polynomial time, how `NP` collects problems whose solutions can be *verified* in polynomial time (even if finding them might be slow), and how `NP-Complete` and `NP-Hard` capture the hardest problems in `NP` and beyond. You will meet famous examples (Traveling Salesman, SAT, the knapsack problem), get a light introduction to **polynomial-time reductions** as the tool used to prove a new problem is `NP-Complete`, and confront the legendary `P vs NP` question along with why it matters for cryptography and the entire structure of computer science. This lesson assumes you are fluent with all the basic asymptotic machinery from **Asymptotic Analysis Fundamentals**, **Big-O Notation (Upper Bound)**, **Time Complexity Analysis Techniques**, **Space Complexity Fundamentals**, and **Little-o and Little-omega Notations**. Complexity classes use those same growth-rate ideas to draw lines between "polynomial" and "exponential" rather than between specific functions like `n^2` and `n log n`. From here you will move into **Amortized Analysis**, shifting from broad problem classification back to the fine-grained per-operation analysis that complex data structures demand.

When a paper claims an algorithm runs in `O(n^2)`, that statement leaves a question wide open: does the algorithm *actually* take quadratic time, or could the bound be loose? **Little-o** and **little-omega** are the notations that close that gap. `f(n) = o(g(n))` says `f` grows *strictly* slower than `g`, never matching its rate, and `f(n) = omega(g(n))` says `f` grows strictly faster. They are the precision tools of theoretical CS. This lesson defines both notations using the formal limit-based criterion: `f(n) = o(g(n))` iff `lim f(n)/g(n) = 0`, and `f(n) = omega(g(n))` iff `lim f(n)/g(n) = infinity`. You will prove and disprove `o` and `omega` claims for common function pairs (`n` vs `n^2`, `log n` vs `n`, `n` vs `n log n`, `2^n` vs `n^k`), use these notations to rank growth rates strictly, and see how the full five-notation system fits together: `O` and `Omega` allow equality, `Theta` requires it, while `o` and `omega` forbid it. This lesson builds on three earlier asymptotic foundations. From **Big-O Notation (Upper Bound)** you have non-strict ceilings; from **Big-Omega Notation (Lower Bound)** you have non-strict floors; and from **Big-Theta Notation (Tight Bound)** you have the exact-rate case. Little-o and little-omega simply require the inequality to be strict, ruling out the matching case that Big-O and Big-Omega permit. With all five notations under your belt, you will be ready for **Complexity Classes (Conceptual Overview)**, where these comparisons get used to separate classes like `P` and `NP`.

Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo `10^9 + 7`", and you will find the same machinery underneath: **modular arithmetic**, the math of working with remainders rather than full integers. It is the bridge between number theory and a huge swath of real algorithms. This lesson develops that machinery from first principles. You will revisit the `mod` operation precisely (including its relationship to division and remainders), then prove and use the addition, subtraction, and multiplication rules that let you take `mod` at every step of a long calculation without changing the answer. From there you will implement **fast modular exponentiation** in `O(log n)` time using binary exponentiation, compute **modular inverses** with **Fermat's Little Theorem** when the modulus is prime, and see exactly why hash tables, RSA, and contest problems rely on these tricks to avoid overflow and to invert multiplications. This lesson builds on **Number Theory Fundamentals**, where you learned about primes, divisibility, `gcd`, and the Euclidean algorithm. Modular arithmetic uses all of those: primality lets you apply Fermat, `gcd` decides when an inverse exists, and divisibility underlies every congruence. From here the only foundations topic remaining is **Basic Proof Techniques**, where you will learn the proof tools (induction, contradiction, contraposition) that make the kinds of arguments you have just been waving at fully rigorous.

When you stare at merge sort or binary search, the running time is not naturally a simple sum like `n^2/2 + n/2`. It is something more interesting: the cost of a problem of size `n` is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a **recurrence relation**, an equation of the form `T(n) = ...` written in terms of `T` on smaller inputs. This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their `T(n)` equations: factorial gives `T(n) = T(n-1) + 1`, binary search gives `T(n) = T(n/2) + 1`, merge sort gives `T(n) = 2 T(n/2) + n`, and naive Fibonacci gives `T(n) = T(n-1) + T(n-2) + 1`. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces. This lesson builds on **Big-O Notation (Upper Bound)**, which gave you the language for expressing complexity, and on **Mathematical Sequences**, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded. Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, **Solving Recurrence Relations**.

Writing the recurrence `T(n) = 2 T(n/2) + n` for merge sort is the easy part. Turning it into the closed-form `O(n log n)` is where the real algorithm analysis happens, and it is exactly what this lesson is for. **Solving Recurrence Relations** gives you a small toolkit that, used well, can analyze nearly every recursive algorithm you will meet in interviews, papers, or production. This lesson walks through five methods. The **Substitution Method** has you guess the solution and prove it by induction, useful when you already suspect the bound. The **Recursion Tree Method** visualizes work level by level and sums it; this is how you see why merge sort spends `n` work per level over `log_2(n)` levels. The **Master Theorem** mechanically solves the divide-and-conquer form `T(n) = a T(n/b) + f(n)` via three cases, and you will memorize when each case fires. The **Extended Master Theorem** patches the gap when `f(n)` includes logarithmic factors. The **Akra-Bazzi Method** generalizes to unequal subproblem sizes that the basic theorem cannot handle. You will practice picking the right tool for each recurrence rather than blindly reaching for the same one every time. This lesson directly continues **Recurrence Relations**, where you learned to write `T(n)` from recursive code, and reuses ideas from **Big-O Notation (Upper Bound)** and **Mathematical Sequences** for the underlying summation arguments. With the analysis sub-track complete, you will pivot back to advanced math in **Modular Arithmetic**, where number-theoretic tools meet algorithm design.

A modern hard drive reads about 100 MB per second sequentially, but a single random seek still costs around 10 milliseconds; that gap is roughly seven orders of magnitude. A binary tree of a billion keys has 30 levels, which means 30 random seeks per lookup. **B-Trees and B+ Trees** keep each node fat enough to fill a disk page, branch into hundreds of children, and answer the same lookup in three or four seeks. That is why every relational database you have used relies on this family for its indexes. This lesson covers the B-Tree minimum-degree parameter `t` and the resulting key-and-child counts at every node, the proactive split during insert that keeps the height bounded by `O(log_t n)`, the merge-or-redistribute logic for delete, and the B+ Tree refinement that pushes all data to the leaf level and links those leaves together so range queries become a sequential scan after a single descent. In **Binary Search Tree (BST)**, every node held a single key and at most two children; that geometry is fine for memory but disastrous for disk because each comparison forces a separate I/O. B-Trees flip the design: keep every node wide so a single I/O resolves many comparisons at once. Next, **Splay Tree** explores a third self-balancing strategy in which the tree reshapes itself around access patterns rather than maintaining strict structural invariants.

Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with `O(n)` search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a **Balanced BST** does. AVL and Red-Black trees are the two most influential designs in this family. This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict `|bf| <= 1` invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ `std::map` and Java `TreeMap`, and analyze the height bound (`<= 2 log n`) that gives both their worst-case `O(log n)` guarantee. In **Binary Search Tree (BST)**, you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting `O(n)` worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant. Next, **B-Trees and B+ Trees** generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.

A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a **Fenwick Tree** (also called a Binary Indexed Tree, or BIT) is the right answer. This lesson covers the dynamic prefix-sum problem (static prefix sums are `O(1)` query and `O(n)` update; you want both in `O(log n)`), the `i & -i` lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in `O(log n)`, and the `prefix(R) - prefix(L-1)` identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting `O(log n)` range updates with `O(log n)` point queries. In **Arrays & Strings**, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. **Segment Tree** solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice. Next, **Sparse Table** addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with `O(1)` queries when no updates are involved.

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.

Range minimum queries on a fixed array do not need updates, so the segment tree's `O(log n)` query is leaving performance on the table. A **Sparse Table** flattens the query down to genuine `O(1)`: precompute the minimum of every power-of-2 length window, and any range `[L, R]` can be answered by combining two such windows that together cover it, exploiting the fact that `min(min(A), min(B)) = min(A union B)` when the windows overlap. This lesson covers the `O(n log n)` preprocessing that fills a 2D table indexed by `(start, log2_length)`, the `O(1)` query trick for idempotent operations such as min, max, GCD, and bitwise OR, the `log2_floor` precomputation that makes every query branch-free, and the slower `O(log n)` query needed when the operation is not idempotent (like sum). You will see why this structure is the right tool for the Range Minimum Query (RMQ) problem and an essential building block in algorithms like Lowest Common Ancestor in `O(1)` per query. In **Arrays & Strings**, a flat array stored values; here the same shape stores precomputed answers indexed by a length exponent. **Logarithms & Exponentiation** is what makes the geometry work: power-of-two windows tile the index space the way binary representations tile integers, and the `O(1)` query depends on `floor(log2(length))`. With Sparse Tables in your toolkit, the curriculum next pivots to specialized structures for strings, immutability, and bounded integer universes.

Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A **Splay Tree** turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay `O(1)` after the first hit. This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields `O(log n)` per operation across any sequence of `m` operations even though individual operations can be `O(n)` in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition. In **Binary Search Tree (BST)**, accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere. Next, **Treap (Randomized BST)** keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.

Genome alignment tools like BWA and Bowtie find a 100-character read inside a 3-billion-base human reference in milliseconds, not by scanning the genome but by querying an index built once over all of its suffixes. **Suffix Array / Suffix Tree** is the family of data structures behind that workflow, and the same machinery powers full-text search, plagiarism detection, and the BWT-based compression in bzip2. This lesson covers the suffix array (a sorted array of starting positions of every suffix), the binary-search pattern match in `O(m log n)` for a pattern of length `m`, the LCP (Longest Common Prefix) array that captures shared prefixes between adjacent sorted suffixes, and the suite of substring problems the pair solves: longest repeated substring, number of distinct substrings, and longest common substring. You will also meet the suffix tree, a compressed trie of all suffixes that pushes pattern matching down to `O(m)` independent of text length, and weigh the suffix array's smaller memory footprint against the suffix tree's faster query. In **Arrays & Strings**, sorting and binary search worked over numbers; here the same primitives extend to strings, with a comparator that compares characters position by position. **Trie (Prefix Tree)** introduced the prefix-matching tree shape, and a suffix tree is a compressed trie built from every suffix of the input. Next, the curriculum explores data structures organized around a different axis entirely: preserving every historical version of themselves through time.

Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A **Treap** reaches the same expected `O(log n)` height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once. This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected `O(log n)` height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: `split(key)` cuts the treap into 'less than' and 'greater or equal' pieces, and `merge` glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting `O(log n)` insert-at-index and slicing. In **Binary Search Tree (BST)**, you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots. With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Iterating over all subsets of every subset of an `n`-element set sounds like `4^n` work. The actual cost is `3^n`: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution. **Advanced Bit Manipulation** collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the `for (s = mask; s > 0; s = (s - 1) & mask)` template, and master bit tricks like isolating the lowest set bit with `x & -x`, turning it off with `x & (x - 1)`, counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling. In **Bit Manipulation (Intro)**, you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium. Next, **Complexity & Proof Intuition (Optional)** revisits the theoretical foundations behind everything built so far.

Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A* with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand. Both algorithms use the same priority-queue framework; the only difference is that A* adds a heuristic estimate to the cost function and biases the search toward the goal. That single addition is what powers GPS, game-pathfinding, and motion planning in robotics. **Advanced Search Algorithms** covers the search refinements that go beyond plain BFS and DFS. You will implement A* with the `f(n) = g(n) + h(n)` cost function, derive what makes a heuristic admissible, and prove the optimality guarantee under admissibility. Bidirectional search runs BFS from both source and target until the frontiers meet, cutting `O(b^d)` to `O(b^(d/2))`. Iterative Deepening DFS combines BFS-style completeness with DFS-style `O(d)` memory, using repeated depth-limited DFS. The lesson finishes with two specialized array searches: Jump search at `O(sqrt(n))` for sorted arrays where binary search is awkward, and interpolation search at `O(log log n)` expected for uniformly distributed keys. In **BFS & DFS (Intro)**, you wrote the basic skeletons. **Graph Algorithms (Core)** introduced Dijkstra's priority-queue relaxation, which A* generalizes by adding the heuristic. Next, **Game Theory** turns to two-player adversarial search.

Finding the lowest common ancestor of two nodes by walking up parent pointers is `O(n)` per query, fine if you ask once but ruinous if you ask a million times on a tree of a million nodes. Binary Lifting precomputes the `2^k`-th ancestor of every node in `O(n log n)` total, then answers LCA in `O(log n)` per query. The same compute-once-then-query-fast pattern unlocks an entire family of advanced tree algorithms. **Advanced Tree Algorithms** covers that family. You will implement LCA via Binary Lifting and via the Euler Tour plus Range Minimum Query approach, where flattening the tree turns subtree queries into array-range queries. Heavy-Light Decomposition splits the tree into chains so path queries become `O(log^2 n)` segment-tree operations. Centroid Decomposition splits a tree of `n` nodes into `O(log n)` layers and powers distance and path-counting queries. The lesson finishes with the rerooting technique for tree DP, which computes DP results for every choice of root in linear total time instead of the naive `O(n^2)`. In **Tree Algorithms**, you mastered recursion-based tree problems and BST operations. This lesson trades simple recursion for preprocessing-and-query structures on top of the tree. Next, **Advanced Search Algorithms** revisits BFS and DFS with heuristic refinements.

Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the approximation ratio, is the difference between a heuristic that might be terrible and an algorithm with a written contract about how far from optimal its answer can be. **Approximation Algorithms** introduces that contract-based view of NP-hard optimization. You will define approximation ratio formally and walk through the classic constant-factor algorithms: a 2-approximation for Vertex Cover via greedy maximal matching, an `O(log n)`-approximation for Set Cover via greedy element-counting, and a 2-approximation for Metric TSP that exploits the triangle inequality on top of an MST. The lesson then covers approximation schemes (PTAS, polynomial in `n` for any fixed `epsilon`; FPTAS, polynomial in both), with Knapsack FPTAS as the canonical example. Throughout, the lesson contrasts approximation algorithms with heuristics, where heuristics give no guarantee at all. In **Greedy (Intro)**, you saw simple greedy strategies and their correctness proofs. **Dynamic Programming (Advanced)** introduced 0/1 Knapsack as an NP-hard exact algorithm. This lesson asks the next question: when exact is too slow, how close to optimal can we provably get? Next, **Advanced Bit Manipulation** turns to bit-level tricks for `O(1)` and bitmask-DP solutions.

0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound. **Branch and Bound** introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach. In **Backtracking (Intro)**, you walked an implicit decision tree with choose, explore, unchoose. **Greedy (Intro)** taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other. Next, **Divide and Conquer (Advanced)** turns to algebraic D&C tricks like Karatsuba and Strassen.

Comparison-based sorting cannot do better than `O(n log n)`. That is not a statement about merge sort or quick sort or any specific algorithm; it is a statement about every possible algorithm in this model, including ones nobody has invented yet. The proof is a counting argument over decision trees, and learning to read it changes how you reason about algorithmic limits forever. Lower bounds, NP-completeness, P versus NP, and loop invariants all live in the same theoretical neighborhood. **Complexity & Proof Intuition (Optional)** is an enrichment tour of that neighborhood. You will use loop invariants to prove iterative algorithms correct, revisit amortized analysis with the potential method, work through NP-completeness via polynomial-time reductions and the Cook-Levin theorem, examine the P vs. NP question and its implications, derive the `Omega(n log n)` comparison-sorting lower bound via decision trees, and meet the broader complexity zoo (co-NP, PSPACE, EXP). This lesson rests on three earlier ideas. **Asymptotic Analysis Fundamentals** gave you the language of growth rates that complexity classes refine. **Dynamic Programming (Intro)** and **Greedy (Intro)** showed you exact polynomial-time algorithms; this lesson asks which problems will never have one. This concludes the algorithms track. From here, the natural next step is sustained problem solving on hard interview problems and competitive programming contests that exercise the full toolkit you have built.

The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment intersection, and point-in-polygon tests all reduce to a sequence of cross-product evaluations with a careful eye on edge cases. Get the geometric primitive right and the rest of the field follows. **Computational Geometry** introduces those primitives and the algorithms built on them. You will start with cross products and the orientation test, then implement convex-hull algorithms three ways: Graham scan in `O(n log n)` (sort by polar angle, maintain a stack with the orientation invariant), Jarvis march in `O(nh)` for hulls with few vertices, and Andrew's monotone chain. The lesson then covers line-segment intersection, the sweep-line algorithm for many segments, the closest-pair-of-points algorithm in 2D, polygon computations using the Shoelace formula, and the ray-casting point-in-polygon test. In **Sorting (Elementary)**, you learned the comparison-based sorting that drives polar-angle preprocessing. **Divide and Conquer (Advanced)** taught you the closest-pair `O(n log n)` template via the strip combine step, which reappears here. Next, **Advanced Tree Algorithms** moves from planar geometry back to hierarchical structures with Binary Lifting and centroid decomposition.

Multiplying two `n`-bit integers the way you learned in school takes `O(n^2)` digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to `O(n^1.585)`. A few years later Strassen pulled the same trick on matrix multiplication, replacing eight recursive multiplications with seven and breaking the `O(n^3)` barrier for the first time. Both algorithms are pure divide-and-conquer with cleverly engineered combine steps, and they remain the gateway to a deeper view of D&C as algebraic restructuring. **Divide and Conquer (Advanced)** walks through that view. You will derive Karatsuba multiplication and apply the Master Theorem to its `T(n) = 3T(n/2) + O(n)` recurrence. You will work through Strassen's seven-multiplication identity for `2 x 2` blocks and discuss when its higher constant factor pays off in practice. You will solve closest-pair-of-points in 2D in `O(n log n)` via the strip optimization in the combine step, and look at convex-hull computation through a divide-and-conquer lens. In **Divide and Conquer (Intro)**, you applied the Master Theorem to merge sort and quick sort. **Recursion Fundamentals** gave you the call-stack model these algorithms still inhabit. This lesson keeps the recurrence framework but engineers cleverer combine steps. Next, **Mathematical Algorithms** turns to number-theoretic computation.

Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has `m * n` cells, each filled by looking at three neighbors. That single 2D recurrence is the gateway to a much larger family: longest common subsequence, knapsack, palindrome partitioning, regex matching, and many more. **Dynamic Programming (Advanced)** is where 1D DP graduates into the rest of the field. You will work through 2D grid and string DP (unique paths, edit distance, LCS, longest common substring), the knapsack family (0/1, unbounded, subset sum, coin change), sequence DP (LIS in `O(n^2)` and the patience-sorting `O(n log n)` variant, maximum product subarray, word break), string DP (palindromic subsequence and substring, regex and wildcard matching), DP on trees (diameter, max path sum, binary tree cameras), interval DP via matrix chain multiplication, and an introduction to bitmask DP for TSP and assignment problems. In **Dynamic Programming (Intro)**, you learned to define state, transition, and base cases on linear problems. This lesson layers a second dimension onto each. Next, **Advanced DP Techniques** introduces optimization tools that push DP beyond standard tabulation.

Standard tabulation gets you `O(n^2)` DP. The Convex Hull Trick brings the same recurrence down to `O(n log n)` whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with `n = 10^5` go from too-slow to fast enough on exactly that change. A whole sub-field of DP is dedicated to these recurrence-shaped optimizations, and this lesson is your entry into it. **Advanced DP Techniques** covers four directions of post-tabulation DP. Optimization methods include the Convex Hull Trick (offline sorted-slope and online Li Chao tree), Divide and Conquer DP for monotone-split problems, and Knuth's Optimization for optimal-BST-style recurrences. Digit DP teaches you how to count numbers with properties in a range `[L, R]` by carrying a tight-constraint flag through the recursion. Advanced bitmask DP solves TSP, Hamiltonian path, and grid-tiling profile DP. Probability DP turns recurrences over expected values into clean tables, and Kadane's algorithm generalizes to circular and 2D variants. In **Dynamic Programming (Advanced)**, you mastered multi-dimensional state and transitions. This lesson asks the next question: when the table is too big or the transition too slow, how do you optimize? Next, **Graph Algorithms (Advanced)** brings similar depth to graph theory.

Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game. **Game Theory** introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique. In **Dynamic Programming (Intro)**, you learned to recurse on subproblems and cache results. **Recursion Fundamentals** gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search. Next, **Randomized Algorithms** turns to a different way of taming worst-case inputs.

Dijkstra's shortest-path algorithm silently assumes every edge weight is non-negative. Hand it a graph with one negative edge and it can produce a wrong answer with full confidence, because the greedy choice that drives the algorithm no longer reflects the true cost. Real graphs (financial arbitrage detection, currency exchange, time-aware routing) routinely contain negative edges, and that single gap motivates an entire second wave of graph algorithms. **Graph Algorithms (Advanced)** covers that wave. Minimum-spanning-tree algorithms include Kruskal's (sort edges and union components) and Prim's (grow a tree using a priority queue), along with the cut property that explains why both produce the same minimum weight. Shortest paths gain Bellman-Ford for negative edges and negative-cycle detection, plus Floyd-Warshall for all-pairs shortest paths in `O(V^3)`. Strongly connected components are tackled by Kosaraju's (two DFS passes) and Tarjan's (single DFS with low-link values). The lesson also covers articulation points, bridges, Euler paths and circuits via Hierholzer's algorithm, and a first conceptual look at NP-complete Hamiltonian paths. In **Graph Algorithms (Core)**, you implemented Dijkstra, topological sort, and cycle detection. **Union-Find (Disjoint Set Union)** gave you the near-constant-time merge-and-query primitive that makes Kruskal's MST run in `O(E log E)`. From here, **Advanced Graph Algorithms (Network Flow)** turns to capacity-constrained optimization on directed graphs.

"For each element in the array, find the next greater element" is a brute-force `O(n^2)` problem until you notice that a stack maintained in decreasing order lets you answer every query as a side effect of a single left-to-right scan. The whole algorithm runs in `O(n)`, and the same monotonic-stack pattern solves trapping rain water, largest rectangle in a histogram, stock spans, and a long tail of related problems with the same template. **Advanced Greedy & Data Structures** is where greedy thinking meets specialized scaffolding. You will implement the monotonic stack pattern for next-greater and next-smaller variants, the monotonic deque for sliding-window maximum and minimum (also a key DP optimization), and sweep-line algorithms for interval and event problems (meeting rooms, interval merge, rectangle area union). The lesson closes with advanced greedy problems that need a heap or priority queue: full Huffman encoding, task scheduling with cooldown, the gas station problem, and activity selection with deadlines and profits. In **Greedy (Intro)**, you saw simple greedy strategies that needed only sorting. **Heaps & Priority Queue** taught you `O(log n)` access to the minimum or maximum, which is exactly what these advanced greedy patterns rely on for their efficiency. Next, **Branch and Bound** extends backtracking with the same kind of bounding-function pruning, applied to optimization search trees.

Computing `a^b mod m` for `a = 7`, `b = 10^18`, and `m = 10^9 + 7` looks impossible: even iterating one multiplication per step would take longer than the age of the universe. Binary exponentiation does it in 60 multiplications, by squaring the base while halving the exponent. RSA encryption depends on exactly this trick, and so do most modular-arithmetic problems in competitive programming. **Mathematical Algorithms** assembles the standard toolkit. You will implement the Sieve of Eratosthenes for primes up to `N` in `O(N log log N)`, plus the segmented sieve for large ranges. Binary exponentiation handles `a^b mod m` in `O(log b)`, and the matrix-exponentiation generalization computes Fibonacci or any linear recurrence in `O(log n)`. You will derive the Extended Euclidean algorithm for `ax + by = gcd(a, b)` and use it for modular inverses, walk through the Chinese Remainder Theorem, compute Euler's totient, apply Fermat's Little Theorem to modular inversion, and run the Miller-Rabin probabilistic primality test. In **Number Theory Fundamentals**, you saw GCD, primes, and divisibility. **Modular Arithmetic** introduced congruences and modular inverses. This lesson turns those facts into algorithms that scale to numbers the problem statement actually asks about. Next, **Computational Geometry** turns to algorithmic problems on points, lines, and polygons.

Two seemingly different problems, the maximum amount of water you can push from a source to a sink through a network of capacitated pipes, and the minimum total capacity you must remove to disconnect the sink from the source, turn out to have the same answer for every graph. The max-flow min-cut theorem ties them together, and once you accept it a surprising number of optimization problems (image segmentation, project selection, bipartite matching) collapse into max-flow instances. **Advanced Graph Algorithms (Network Flow)** introduces the algorithms that compute that maximum flow. You will work through the Ford-Fulkerson method built on augmenting paths and the residual graph, the BFS-based Edmonds-Karp variant with its `O(V * E^2)` guarantee, and Dinic's algorithm which uses level graphs and blocking flows to reach `O(V^2 * E)`. The lesson then turns to maximum bipartite matching (Hungarian and Hopcroft-Karp), applications like airline scheduling and image segmentation, and a first look at minimum-cost flow. In **Graph Algorithms (Advanced)**, you handled MST, all-pairs shortest paths, and SCCs on edge-weighted graphs. Network flow keeps the weighted-edge model but flips the question from "shortest" to "highest throughput." Next, **String Algorithms** turns to pattern matching, the implicit automaton of a regular expression.

Boyer-Moore is the algorithm `grep` actually uses, and it has a counterintuitive property: longer patterns make it _faster_, not slower, because the bad-character rule lets it skip whole chunks of the text without inspecting them. The best case is `O(n / m)`, sublinear in the text length. The same insight (start from the right, jump aggressively on mismatch) defines a different family of pattern-matching algorithms from the linear-scan family of KMP and Z. **Pattern Matching Algorithms** rounds out the string-search toolkit. You will implement Boyer-Moore with both the bad-character rule and the good-suffix rule, build a deterministic finite automaton (DFA) from a pattern and use the resulting state-transition table for `O(n)` matching after `O(m * |alphabet|)` preprocessing, and extend pattern search into two dimensions row by row. The lesson closes with a head-to-head comparison of every string-matching algorithm you have seen so far (KMP, Z, Rabin-Karp, Manacher, Aho-Corasick, Boyer-Moore, DFA), so you can pick the right tool for any matching task: long patterns, multi-pattern, streaming, or 2D. In **String Algorithms**, you mastered the failure-function family of linear-time matchers. This lesson adds the right-to-left family and the automaton-construction family. From here, **Advanced Greedy & Data Structures** turns to monotonic stacks.

Plain quick sort with a fixed pivot is `O(n log n)` on random input but `O(n^2)` on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes `O(n log n)` _expected_ on every input, because the adversary no longer knows where the algorithm will partition. Randomization is not a hack here; it is a principled way to break the dependency between input and runtime. **Randomized Algorithms** trains that style of thinking. You will distinguish Las Vegas algorithms (always correct, randomized running time) from Monte Carlo algorithms (bounded running time, possibly wrong) and reason about expected-value guarantees. You will analyze Randomized Quick Sort to see why expected `O(n log n)` is robust against adversarial input, implement Quick Select for `O(n)` expected-time kth-element selection plus the deterministic median-of-medians variant, and walk through Reservoir Sampling Algorithm R for uniformly sampling `k` elements from a stream of unknown length, including the proof of uniformity. The lesson also revisits skip lists and treaps from the data-structures track as randomized alternatives to balanced BSTs. In **Sorting (Elementary)**, you saw worst-case-sensitive sorting. **Recursion Fundamentals** gave you the call-stack model behind quick sort and quick select. This lesson injects controlled randomness into those frameworks. Next, **Approximation Algorithms** trades exactness for polynomial time on NP-hard inputs.

Naive substring search compares the pattern against every position in the text, restarting from scratch on each mismatch, for `O(n * m)` worst-case time. KMP, by precomputing where to resume after a mismatch, never restarts. The text pointer moves forward strictly monotonically, the pattern pointer is corrected by a failure function, and the whole search runs in `O(n + m)`. That single insight defines a family of linear-time string algorithms that power editors, search engines, and bioinformatics pipelines. **String Algorithms** covers that family. KMP teaches you to build the failure function (prefix function) and use it to skip redundant comparisons. The Z algorithm offers an alternative `O(n)` framework based on the Z-array. Rabin-Karp introduces rolling hashes for multi-pattern search and is the backbone of plagiarism detection. Manacher's algorithm finds the longest palindromic substring in linear time using a clever transform with separators. Aho-Corasick generalizes KMP to multiple patterns simultaneously by adding failure links to a trie, producing a finite automaton that scans the text once. In **Arrays & Strings**, you treated strings as arrays of characters with `O(1)` indexed access. **Hash Map (Dictionary) Basics** gave you the `O(1)` lookup used by Rabin-Karp. This lesson layers algorithmic structure on top of those primitives. Next, **Pattern Matching Algorithms** extends the toolkit with Boyer-Moore, DFA-based matching, and 2D pattern search.