The primary topics in this part of the specialization are: asymptotic («Big-oh») notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

The Program 

Introduction; «big-oh» notation and asymptotic analysis

1. Why Study Algorithms?
2. Integer Multiplication.
3. Karatsuba Multiplication.
4. About the Course.
5. Merge Sort: Motivation and Example.
6. Merge Sort: Pseudocode.
7. Merge Sort: Analysis.
8. Guiding Principles for Analysis of Algorithms.
9. The Gist.
10. Big-Oh Notation.
11. Basic Examples.
12. Big Omega and Theta.

Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms

1. O (n log n) Algorithm for Counting Inversions I.
2. O (n log n) Algorithm for Counting Inversions II.
3. Strassen’s Subcubic Matrix Multiplication Algorithm.
4. O (n log n) Algorithm for Closest Pair I.
5. O (n log n) Algorithm for Closest Pair II.

The QuickSort algorithm and its analysis; probability review

1. Quicksort: Overview.
2. Partitioning Around a Pivot.
3. Correctness of Quicksort.
4. Choosing a Good Pivot.
5. Analysis I: A Decomposition Principle.
6. Analysis II: The Key Insight.
7. Analysis III: Final Calculations.
8. Probability Review I.
9. Probability Review II.

Linear-time selection; graphs, cuts, and the contraction algorithm

1. Randomized Selection. Algorithm.
2. Randomized Selection. Analysis.
3. Deterministic Selection. Algorithm.
4. Deterministic Selection. Analysis I.
5. Deterministic Selection. Analysis II.
6. Omega (n log n) Lower Bound for Comparison. Based Sorting.
7. Graphs and Minimum Cuts.
8. Graph Representations.
9. Random Contraction Algorithm.
10. Analysis of Contraction Algorithm.
11. Counting Minimum Cuts.