Divide and Conquer, Sorting and Searching, and Randomized Algorithms (Coursera)

Divide and Conquer, Sorting and Searching, and Randomized Algorithms (Coursera)

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).

Syllabus

Week 1

Introduction; “big-oh” notation and asymptotic analysis.

Week 2

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

Week 3

The QuickSort algorithm and its analysis; probability review.

Week 4

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

Teacher

Tim Roughgarden