Five Things I Learned from Dick Karp
summary
Shows five concrete lessons: a one-line indicator proof that the expected number of quicksort comparisons equals the sum of 2/(j-i+1) giving ~2n ln n; a randomized marking algorithm that cuts caching competitiveness from K to O(H_K) under an oblivious adversary; an incremental random-split search tree that matches optimal cost for unknown query count R; commute time = 2|E|·effective electrical resistance; and a torus-based content‑addressable network that scales and is used at trillion‑file, million‑node scale.
AI-written summary · about
chapters (6)
- 0:00Five things I learned from Dick Karp Prabhakar Raghavan, Google
- 0:36Elegance in simplicity
- 5:07The power of randomization
- 10:51The power of deferral
- 14:44Everything is connected
- 19:47Utility
related talks
59mTop 10 Algorithms for Coding Interviews
01h 52mThe evolving search for effective C++ - Keynote
45mI Finished the 9 Advents of Code: Lessons Learned
52mCompSci and My Day Job
01h 01mDown the Rabbit Hole: An Exploration of Stack Overflow Questions
26mRuby as Art; Ruby as Science; Ruby as Craft
50mCompSci and My Day Job
06mLightning Talk: How to Win at Coding Interviews