Lecture 8: Streaming and Sketching Algorithms (Part 1)

Dr. Jelani Nelson introduces a simple streaming algorithm (Morris' Algorithm) to store a counter and discusses common tools and techniques for runtime and space analysis. 0:00 Streaming setting, approximating numbers 23:50 Morris' Algorithm and start of analysis 36:05 Review of probability tools (concentration inequalities) 49:20 Finishing analysis of Morris' Algorithm 57:23 Improvements on Morris' Algorithm 1:13:50 Bound for approximate counting