Divide and Conquer

Jesus A. Gonzalez

July 17, 2019

Divide and Conquer

Divide and Conquer

Recurrences

Recurrences

Recurrences

Recurrences

Recurrences

Recurrences

Technicalities in Recurrences

The Maximum-subarray Problem

The Maximum-subarray Problem

The Maximum-subarray Problem

The Maximum-subarray Problem

A Brute-force Solution

A Transformation

A Transformation

A Solution Using Divide-and-conquer

A Solution Using Divide-and-conquer

A Solution Using Divide-and-conquer

A Solution Using Divide-and-conquer

A Solution Using Divide-and-conquer

Analyzing the Divide-and-conquer Algorithm

A Solution Using Divide-and-conquer

A Solution Using Divide-and-conquer

The Substitution Method for Solving Recurrences

The Substitution Method

The Substitution Method: Example

The Substitution Method: Example

The Substitution Method: Example

The Substitution Method: Example

Making a Good Guess

The Recursion-tree Method for Solving Recurrences

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Recursion-tree Method

The Master Method for Solving Recurrences

The Master Method

The Master Method

The Master Method

The Master Method

The Master Method

The Master Method