$
Learning Paths - Coming Soon
The routes, quizzes and progress tracking are built, but most of the series they thread together are still being written. This module opens once enough of that content is live. Back soon.
⚠

This module is currently being developed and will be available soon. Check back later for updates.

→Status: In Development
✓Planning phase completed
⟳Development in progress...
○Testing pending
./learning-paths

Algorithms Under a Handicap

Seven ways to compute well when you are missing something: memory, certainty, the future, or an honest input.

Rolling out

# Recognize which classic handicap a hard problem imposes (limited memory, no randomness, no future, NP-hardness, only a small parameter, or selfish inputs) and reach for the master technique each one demands.

Want to Learn → Deep DiveAlgorithms53 posts7h 56m core · 11h 28m full2/39 live
0/39 core steps done0%
Start path

# a suggested order, not a lock: jump anywhere, checkpoints track what you finish

  1. Algorithms Under a Handicap: A Field GuideWant to Learn11 min scheduledquiz

    The field guide: why a handicap is a design principle, not just an obstacle, and what unites the seven paradigms.

  2. start here
    Online Algorithms8 posts · 1h 35m

    Handicap: decisions are irrevocable and the future is hidden. Measure yourself against the offline optimum with the competitive ratio. The most intuitive handicap, and the one that names the whole tour, so the field guide opens here.

    1. Deciding Without the Future: An Introduction to Online AlgorithmsDeep Dive11 min
    2. Ski Rental: The Rent-or-Buy DecisionDeep Dive12 min
    3. Paging: Choosing What to Evict, BlindDeep Dive12 mincoming soon
    4. Self-Organizing Lists: Move-to-FrontDeep Dive10 min scheduled
    5. Load Balancing: Greedy Scheduling on Many MachinesDeep Dive13 min scheduled
    6. Online Matching: Ads, Randomness, and the Number 1 - 1/eDeep Dive12 min scheduled
    7. Lower Bounds and Yao's Principle: Proving the WallDeep Dive13 min scheduled
    8. The Price of Not Knowing the Future: What the Series Was Really AboutDeep Dive12 min scheduled
  3. Randomized Algorithms9 posts · 1h 56m

    Handicap: a clever adversary picks your worst input. Flip coins so no fixed input is bad, and let concentration turn an average into near-certainty.

    1. A Coin the Adversary Cannot Predict: An Introduction to Randomized AlgorithmsDeep Dive14 min scheduled
    2. Randomized QuickSort: One Random Pivot Beats Every AdversaryDeep Dive13 min scheduled
    3. Concentration: Why an Average Is Almost a CertaintyDeep Dive13 min scheduled
    4. Universal Hashing: A Random Function No Adversary Can BreakDeep Dive13 min scheduled
    5. Skip Lists: A Balanced Search Tree Built From Coin FlipsDeep Dive12 min scheduled
    6. Karger's Min-Cut: Contract Random Edges and HopeDeep Dive13 min scheduled
    7. Fingerprinting: Checking an Answer Without Recomputing ItDeep Dive13 min scheduled
    8. The Probabilistic Method: Proving Things Exist by Flipping CoinsDeep Dive13 min scheduled
    9. Randomness as a Resource: The Randomized Algorithms ToolkitDeep Dive12 min scheduled
  4. Streaming Algorithms9 posts · 1h 47m

    Handicap: the data will not fit and you get one pass. Keep a tiny sketch instead of the stream, and accept a controlled, one-sided error. The hashing and concentration come straight from the randomized toolkit.

    1. Computing on Data You Cannot Keep: An Introduction to Streaming AlgorithmsDeep Dive13 min scheduled
    2. Reservoir Sampling: A Fair Sample Without Knowing the SizeDeep Dive11 min scheduled
    3. HyperLogLog: Counting the UncountableDeep Dive11 min scheduled
    4. Count-Min Sketch: Every Frequency in a Grid of CountersDeep Dive11 min scheduled
    5. Bloom Filters: Membership in a Bit ArrayDeep Dive13 min scheduled
    6. Misra-Gries: Finding the Heavy HittersDeep Dive12 min scheduled
    7. The AMS Sketch: A Stream's Skew from a Tug of WarDeep Dive12 min scheduled
    8. Streaming Quantiles: The Median and the p99 as Data FlowsDeep Dive11 min scheduled
    9. The Streaming Toolkit: One Idea Behind Six StructuresDeep Dive13 min scheduled
  5. Approximation Algorithms8 posts · 1h 41m

    Handicap: the exact answer is NP-hard. Settle for provably near-optimal, with a ratio you can prove.

    1. When Good Enough Is Provably Good: An Introduction to Approximation AlgorithmsDeep Dive14 min scheduled
    2. Vertex Cover: A Matching Is All You NeedDeep Dive13 min scheduled
    3. Set Cover: Greedy Is the Best You Can DoDeep Dive13 min scheduled
    4. Metric TSP: From a Spanning Tree to ChristofidesDeep Dive13 min scheduled
    5. Makespan Scheduling: The Least-Loaded MachineDeep Dive12 min scheduled
    6. Bin Packing: First Fit, and the Trouble with Being ExactDeep Dive12 min scheduled
    7. Knapsack: Coming Arbitrarily CloseDeep Dive11 min scheduled
    8. The Approximation Toolbox: A Few Moves, a Whole SpectrumDeep Dive13 min scheduled
  6. Amortized Analysis3 posts · 41 min

    Handicap: a single operation can be expensive. Pay for the worst case on average and bound a whole sequence with the potential method. The lens that reframes how we even measure cost.

    1. Amortized Analysis: Paying for the Worst Case on AverageDeep Dive15 min scheduled
    2. The Potential Method in Action: Union-Find and Self-Adjusting StructuresDeep Dive13 min scheduled
    3. The Accountant's View: What Amortized Analysis Teaches UsDeep Dive13 min scheduled
  7. Parameterized Complexity7 posts · 1h 31m optional

    Handicap: the problem is NP-hard, but a small parameter hides the difficulty. Confine the blow-up to k with kernelization and bounded search.

    1. Parameterized Complexity: When a Small Parameter Tames a Hard ProblemDeep Dive13 min scheduled
    2. Bounded Search Trees: Branch, Recurse, and Bound by kDeep Dive13 min scheduled
    3. Kernelization: Shrink the Instance Before You Solve ItDeep Dive13 min scheduled
    4. Treewidth: Solving Hard Problems on Almost-TreesDeep Dive13 min scheduled
    5. Color Coding: Finding Small Patterns with a Splash of RandomnessDeep Dive13 min scheduled
    6. The Wall: W[1]-Hardness and the Limits of Fixed-Parameter TractabilityDeep Dive14 min scheduled
    7. The Whole Picture: What Parameterized Complexity Is Really AboutDeep Dive12 min scheduled
  8. Algorithmic Game Theory8 posts · 2h 1m optional

    Handicap: the input has its own agenda. Design the rules so that truth-telling is the selfish choice, and bound the price of anarchy.

    1. When the Input Has a Mind of Its Own: An Introduction to Algorithmic Game TheoryDeep Dive14 min scheduled
    2. The Price of Anarchy: How Much Does Selfishness Cost?Deep Dive15 min scheduled
    3. Stable Matching: A Market With No MoneyDeep Dive16 min scheduled
    4. The Vickrey Auction: The Genius of the Second PriceDeep Dive15 min scheduled
    5. VCG: Truthful Auctions for a Whole MarketDeep Dive14 min scheduled
    6. Myerson's Optimal Auction: Designing for RevenueDeep Dive15 min scheduled
    7. Fair Division: Cutting the Cake When Everyone Wants MoreDeep Dive18 min scheduled
    8. When the Input Fights Back: The Algorithmic Game Theory ToolkitDeep Dive14 min scheduled
  9. Algorithms Under a Handicap CapstoneWant to Learn5 minquiz

    Capstone: one question per handicap. Name the constraint and the master technique it forces, across all seven paradigms.

  10. You can spot the handicap behind a hard problem and name the technique it demands