Welcome to the course webpage of CS6100 !.


F Slot: TUE 17-17:50, WED 11-11:50, THU 9-9:50, FRI: 8-8:50


Online mode. Three live lectures per week through google meet. One lecture will be a recorded session.

Office hours

THU 8-8:50, TUE 15:30-16:30


Beyond worst case analysis of algorithms
The traditional analysis of algorithms focused mainly on worst case complexity of an algorithm. There are algorithms in many disciplines such as Machine Learning, Operations Research and Artificial Intelligence which perform surprisingly well in practice, however, with an exponential worst case complexity. Prime examples are the simplex method for linear programming and the k-means algorithm for clustering. Both perform very well in practice, however, have exponential worst case complexity. This course aims to introduce paradigms of algorithm analysis that explain practical behavior of algorithms. We will be primarily interested in probabilistic and smoothed analysis of algorithms.