Theme: Beyond worst case analysis of algorithms
The traditional analysis of algorithms focussed 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.
- Instructors :
- Teaching Assistants :