Introduction to Algorithms and Analysis

Sorting and the analysis behind it

This 60-lecture NPTEL course from IIT Kharagpur begins with insertion sort and how its running time is analyzed. Asymptotic notation then gives the vocabulary for comparing algorithms, so the rest of the course has a common yardstick.

The main ideas

• Recurrences for divide-and-conquer algorithms, solved by the substitution method and the master method.
• Merge sort, quicksort and its analysis, plus the randomized version.
• Strassen's algorithm for matrix multiplication, placed in the divide-and-conquer block.
• Heaps and heap sort, followed by decision trees.

Who should watch

Students who have written sorting code but not analyzed it will find the recurrence and master method lectures the most rewarding. The decision tree lecture at the end is a good bridge to lower bounds for comparison sorting.