Module: Divide and conquer

Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.

Learning Outcomes

Recognize when divide and conquer is appropriate

Be able to recognize when the divide and conquer algorithm is an appropriate algorithm to apply to a programming problem.

Design divide and conquer algorithms

Successfully design and implement divide and conquer algorithms to solve specific programming problems.


Divide and conquer and recurrence relations

Introduction to the divide and conquer algorithm

Screencast Suthers 14 min

Solving recurrence relations: substitution

How to perform substitution.

Screencast Suthers 8 min

Solving recurrence relations: recursion trees

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

Screencast Suthers 19 min

Solving recurrence relations: master method

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

CLRS 4 - Divide and conquer

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

Textbook 30 pages

Chapter 7 Notes

Notes on divide and conquer


Divide and conquer

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

Screencast Demaine 68 min

Experiential Learning

Understanding master method and substitution

Apply your knowledge of the master method and substitution.