When Computing Time is Time Lost

on YouTube ↗37m

" summary

Two theoretical models appear: one designs fast timers that decide whether a heuristic will exceed a deadline by testing the actual input, the other treats computation time as lost execution time and optimizes the planning/execution split. Concrete tools: random-pair inversion estimator gives a constant‑time, nearly complete timer for bubble sort; Fibonacci‑type inputs certify many steps for Euclid’s GCD; scheduling uses a tau parameter for DP cost and a DP+greedy mix that outperforms full DP when planning eats real time.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:43Real time decision making
3. 2:52Turning Heuristics into Good Algorithms
4. 5:35For correctness ... Program Checkers
5. 6:20Timers: Similar idea for running time
6. 8:49Simple Observations
7. 10:48Probabilistic Timers
8. 13:21Generalizing...
9. 15:49Another example
10. 18:34Other problems with timers
11. 20:49Scheduling
12. 22:46Dynamic Programming for Standard Version
13. 26:11A Better Alternative