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 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
Divide and conquer: binary search, powering a number, fibonacci numbers, matrix multiplication
Screencast Demaine 68 min