algo.org

* Algorithms: Design and Analysis, Part 1

I. INTRODUCTION (Week 1)

Why Study Algorithms ? (4 min)

Integer Multiplication (9 min)

Karatsuba Multiplication (13 min)

About the Course (17 min)

Merge Sort: Motivation and Example (9 min)

Merge Sort: Pseudocode (13 min)

Merge Sort: Analysis (9 min)

Guiding Principles for Analysis of Algorithms (15 min)

II. ASYMPTOTIC ANALYSIS (Week 1)

The Gist (14 min)

Big-Oh Notation (4 min)

Basic Examples (7 min)

Big Omega and Theta (7 min)

Additional Examples [Review - Optional] (8 min)

III. DIVIDE & CONQUER ALGORITHMS (Week 1)

O(n log n) Algorithm for Counting Inversions I (13 min)

O(n log n) Algorithm for Counting Inversions II (17 min)

Strassen’s Subcubic Matrix Multiplication Algorithm (22 min)

O(n log n) Algorithm for Closest Pair I [Advanced - Optional] (32 min)

O(n log n) Algorithm for Closest Pair II [Advanced - Optional] (19 min)

IV. THE MASTER METHOD (Week 2)

motivation (8:00)

Formal Statement (10 min)

Examples (13 min)

Proof I (10 min)

Interpretation of the 3 Cases (11 min)

Proof II (16 min)

V. QUICKSORT - ALGORITHM (Week 2)

Quicksort: Overview (12 min)

Partitioning Around a Pivot (25 min)

Correctness of Quicksort [Review - Optional] (11 min)

Choosing a Good Pivot (22min)

Programming Question - 2

VI. QUICKSORT - ANALYSIS (Week 2)