Kurs Algorithms for Big Data

Aditi Dudeja

With the growing number of massive datasets in applications such as machine learning and artificial intelligence, classical algorithms for processing such datasets are often no longer feasible. In this course we will cover algorithmic techniques and models for handling such data. There will be two main threads:  

First, we will focus on the streaming model which is a model for studying algorithms that process large amounts of data, so large that they will not fit in a computer’s main memory. As we shall see, space constraints force us to rethink even basic algorithmic problems such as counting the number of distinct elements, selection, or sorting. We will also learn various techniques to compress data while retaining essential information. Graphs are used to represent data in various domains such as social networks, chemical and biological networks, and communication networks. Classical graph algorithms suffer from long processing time due to the large real-world graph size. In the second thread, we will look at an important algorithmic concept called graph sparsification, which allows us to greatly improve runtime of existing graph algorithms by substituting the full graph with a sparser graph without degrading the quality of the output. The techniques we will study have numerous applications. 

The objective of this course is to introduce the students to the mathematical underpinnings of big data algorithms. Typically, such courses focus on implementing efficient algorithms, however through this course the student will understand the "why's" of such algorithms.

I am hoping that by the end of the course, 

(1) the students will have a good understanding of the role of various techniques used in algorithms large data sets, 

(2) the student are able to design and analyze algorithms for a wide range of canonical problems studied in this course, and even more importantly, for new problems that the student may have not encountered directly in this course, 

(3) they will take hopefully take home the message that often having the right logical or mathematical angle can make their codes more elegant and functional.