Randomized and Big Data Algorithms

3 Credits.

This course will cover basic methods of randomization for efficient algorithms and relevant techniques of 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.