Part X · Computational Geometry and Advanced Algorithms
60. Randomized, Online and Streaming Algorithms
7 lessons•29 topics•Advanced / Expert
0 of 7 lessons published
60.01Outline
Randomized algorithm analysis
- Las Vegas vs Monte Carlo
- Expected time
- Failure probability
- Amplification
60.02Outline
Randomized selection and sorting
- Randomized quicksort
- Randomized quickselect
- Randomized treaps
- Hash randomization
60.03Outline
Sampling
- Uniform shuffle
- Reservoir sampling
- Weighted reservoir sampling
- Random subset sampling
60.04Outline
Online algorithms
- Online vs offline decisions
- Competitive ratio
- Online interval scheduling
- Paging/caching algorithms
60.05Outline
Streaming statistics
- Running mean/variance
- Running median
- Frequency counters
- Top-k streaming
60.06Outline
Sketching and approximation
- Bloom filter
- Count-Min Sketch
- HyperLogLog
- Misra-Gries
- Heavy hitters
60.07Outline
Distributed/large data context
- Approximate distinct
- Consistent hashing
- Sampling at scale
- Streaming windows