3.0

credits

Average Course Rating

This course will cover fundamental methods of randomization for efficient algorithms and relevant techniques in probabilistic analysis. The first part of the course will discuss classical randomized algorithms, including the randomized algorithm for the min-cut problem, hashing techniques, tail inequalities, and the probabilistic method. The second part will delve into advanced topics such as coreset methods for clustering algorithms, the Johnson-Lindenstrauss lemma, and the applications of streaming and sketching algorithms.