Algorithms

Online Algorithms

This guide helps you get your bearings in Online Algorithms before you start exploring the interactive timeline, framework graph, and concept maps.

Before You Dive In

Online Algorithms addresses a core algorithms question: what can we compute efficiently, and with what guarantees?
Rough timeline: classical design methods -> NP-completeness and intractability -> randomized and approximation methods -> streaming, online, and parameterized frameworks.
Start with reduction and complexity classes; they organize almost every advanced algorithmic argument.
In Noosaga, compare frameworks by objective: exactness, approximation ratio, memory footprint, latency, or communication cost.

ReductionTransforming one problem into another to transfer hardness or algorithmic results.

NP-completenessClass of problems believed to lack polynomial-time exact algorithms.

Approximation algorithmAlgorithm with provable closeness to optimal solution for hard problems.

Randomized algorithmAlgorithm using randomness to improve expected performance or simplicity.

Asymptotic analysisGrowth-rate analysis of runtime or space as input size increases.

Equating asymptotically optimal with practically fastest on real workloads.

Assuming NP-hard means impossible; many instances remain solvable with structure-aware methods.

Treating proofs as optional; guarantees are the defining value of algorithmics.

Open the interactive view and scan the framework timeline. Which frameworks came first? Which ones overlap? Where are the big transitions?

Click into individual frameworks to read what each one claims, where it came from, and how it relates to its neighbors.

See how the key ideas within a framework connect. This is useful for figuring out what to learn first and what depends on what.

Take the quiz for any framework you've read about. It's a quick way to find out whether you actually understood the core ideas or just skimmed them.