Divide and conquer

Learning Outcomes

Use of divide-and-conquer in recurrence relations.
Use of Master Method and Substitution methods to bound runtime behavior of algorithms.

Introduction to the divide and conquer algorithm

Screencast Suthers 14 min

How to perform substitution.

Screencast Suthers 8 min

How to generate a guess for the form of the solution to the recurrence.

Screencast Suthers 19 min

Find solutions to recurrence relations of form T(n) = aT(n/b) + h(n), where a and b are constants, a ≥ 1 and b > 1

Screencast Suthers 17 min

The maximum subarray problem, strassen’s algorithm for matrix multiplication, substitution method, recursion tree method, and the master method.

Textbook 30 pages

Notes on divide and conquer

Notes

Divide and conquer: binary search, powering a number, fibonacci numbers, matrix multiplication

Screencast Demaine 68 min