Basic Information

Traditionally, performance of algorithms are given as worst case guarantees. However, many of the algorithms with bad worst case guarantees tend to perform well in practice. This makes worst-case paradigm insufficient for the development of algorithms that have good performance in real-world scenarios. 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. We will be demonstrating smoothed analysis of algorithms via several examples. We plan to discuss smoothed analysis of algorithms for clustering problems (k-means), travelling salesman problems (TSP) and related Euclidean optimization problems. Average case analysis of algorithms involves analyzing algorithms with respect various input distributions, uniform distribution being one of the primary distributions. Vital to such analysis are structural behavior of a problem under a particular distribution. We will study probability theory for Euclidean optimization problem and its applications for developing algorithms with very good average case guarantees. Finally, we plan to introduce probabilistic analysis of algorithms in the discrete setting. We study algorithms for problems such as matching, shortest paths under random models for graphs. We conclude the course with a thorough discussion of prominent research problems in the area.

Syllabus:

Basics of probability: Markov’s inequality, Chebyshev’s, Chernoff’s, Martingales and Talagrand’s isoperimetry (1 Week)
Smoothed analysis of Algorithms: Knapsack, Integer Programming, TSP: 2-OPT. Smoothed number of pareto optimal solutions. Other local search algorithms. Partitioning algorithm. K-means clustering. Stability: algorithms for stable instances. Perturbation stable clustering. Stable instances.(7 weeks)
Probabilistic Analysis of Algorithms: Probabilistic analysis of Euclidean optimization problems. Concentration bounds. Other probabilistic models. (4 weeks)

Evaluation (To be updated):

Assignments - 20% (2 * 10% )
Midsem - 15% (2 hours exam)
Endsem - 15% (2 hours exam)
Project + Presentation - 50% (One intro meeting(5%) + one review meeting (10%) + viva (10%) + a 45 min presentation (15%) + short report (5%)+ Critique of another presentation and report (5%))