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