Advanced -> Online Algorithms
Competitive analysis for decisions without future knowledge, taught first through deterministic ski-rental threshold policies and then compared against paging and randomized adversaries.
- Topic slug:
advanced/online-algorithms
- Tutorial page: Open tutorial
- Ladder page: Open ladder
- Repo problems currently tagged here:
1
- Repo companion pages:
5
- Curated external problems:
2
Microtopics
- competitive-ratio
- online-algorithm
- ski-rental
- threshold-policy
- adversarial-future
- paging-compare
- randomized-compare
Learning Sources
Follow-Up Reading
Repo Companion Material
Curated External Problems
Core
| Problem |
Source |
Difficulty |
Context |
Style |
Prerequisites |
Tags |
Why it fits |
| Ski Rental Benchmark |
JHU Intro Algorithms |
Theory |
Competitive Analysis |
Competitive Analysis; Theory Benchmark |
Threshold Reasoning; Offline Optimum; Adversarial Analysis |
Ski Rental; Competitive Ratio; Threshold Policy; Adversarial Future |
The canonical first online-algorithms benchmark where the whole lesson is to compare one deterministic threshold policy against the offline optimum. |
Stretch
| Problem |
Source |
Difficulty |
Context |
Style |
Prerequisites |
Tags |
Why it fits |
| Online Algorithms Notes: Ski Rental and Paging |
Stanford CS369 |
Theory |
Paging, Randomized Compare |
Lecture Notes; Theory Breadth |
Ski Rental; Competitive Ratio; Basic Randomized Algorithms |
Competitive Ratio; Randomized Adversary; List Update |
A clean follow-up once ski rental clicks and you want the next canonical online examples plus the randomized paging contrast. |
Repo Problems
| Code |
Title |
Fit |
Difficulty |
Pattern |
Note |
Solution |
SKIRENTAL |
Ski Rental |
primary |
medium |
- |
Note |
Code |
Regeneration
python3 scripts/generate_problem_catalog.py