Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 10 Video [previous] [next]

[+] Randomized algorithms

In this lecture we discuss randomized algorithms. We give a brief review of basic probabiliy theory, inculding the Markov and Chernoff bounds. We discuss a few examples for the use of randomization in sampling (calculating the value of pi), the selection probelm, skip lists, random walks, and finding the minimum cut in a graph.

Download Video: 720p

Lecture notes, page 1/79 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.