Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.
Be able to recognize when the divide and conquer algorithm is an appropriate algorithm to apply to a programming problem.
Successfully design and implement divide and conquer algorithms to solve specific programming problems.
Introduction to the divide and conquer algorithm
Screencast Suthers 14 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
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