Online-Computer-Science-degree

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

by Stanford University

About this Course

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

Project

Calculate the minimum number of cuts by choosing random contraction edges. I implemented this with multithreaded Rust.

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.

Following the online course: https://www.coursera.org/learn/algorithms-divide-conquer