Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.
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
Apply your knowledge of the master method and substitution.
Homework