CSE 421 Section 4

Divide and Conquer

Writing a Divide and Conquer Algo

Divide and Conquer

1. Divide instance into subparts
2. Solve the parts recursively
3. Conquer by “merging” the answers

​

The keys to this strategy:

• Come up with a baseline (usually a brute force algorithm)
• Your “conquer” step must be faster than brute force!
• Once you have your algo, write a recurrence for the runtime
• Your d&c runtime should be BETTER than the baseline runtime

The Strategy (hint: it’s the same as last week!)

1. Read and Understand the Problem
2. Generate Examples
3. Produce a Baseline
4. Brainstorm and Analyze Possible Algorithms
5. Write an Algorithm
6. Show Your Algorithm is Correct
7. Optimize and Analyze the Run Time

Problem 1 – Maximum Subarray Sum

1. Read and Understand the Problem

Reminder of the Questions to Ask:

• What is the input type? (Array? Graph? Integer? Something else?) �

​

​

• What is your return type? (Integer? List?) �

​

​

• Are there any technical terms in the problem you should pay attention to?

Reminder of the Questions to Ask:

• What is the input type? (Array? Graph? Integer? Something else?) �

​

​

• What is your return type? (Integer? List?) �

​

​

• Are there any technical terms in the problem you should pay attention to?

int[]

Reminder of the Questions to Ask:

• What is the input type? (Array? Graph? Integer? Something else?) �

​

​

• What is your return type? (Integer? List?) �

​

​

• Are there any technical terms in the problem you should pay attention to?

int[]

int (the largest sum of any subarray)

Reminder of the Questions to Ask:

• What is the input type? (Array? Graph? Integer? Something else?) �

​

​

• What is your return type? (Integer? List?) �

​

​

• Are there any technical terms in the problem you should pay attention to?

int[]

int (the largest sum of any subarray)

“subarray” means contiguous elements of the array

Key Idea with Divide and Conquer �(and other recursive algorithms)

• If you identify that you want to use a recursive algorithm paradigm like Divide and Conquer, it’s not enough to just answer those key questions on the previous slide�
• Since you know you will have recursive calls, you need to be explicit about what those recursive calls are giving you that, when combined together, gives you the solution you’re looking for�
• You should be clear about the syntax of your recursive calls (i.e. what are the inputs and outputs).

Problem 1.1 – Maximum Subarray Sum

What is the syntax of your recursive calls?

Work through this problem with the people around you, and then we’ll go over it together!

Problem 1.1 – Maximum Subarray Sum

What is the syntax of your recursive calls?

​

Problem 1.1 – Maximum Subarray Sum

What is the syntax of your recursive calls?

Each recursive call of the form SubarraySumDC(A[], i, j) returns the largest sum of a contiguous subarray of A[], with all elements of the subarray occurring between i and j.

2. Generate Examples

Good examples help with understanding now and testing later!

• You should generate two or three sample instances and the correct associated outputs. �
• It’s a good idea to have some “abnormal” examples – consecutive negative numbers, very large negative numbers, only positive numbers, etc.�
• Note: You should not think of these examples as debugging examples – null or the empty list is not a good example for this step. You can worry about edge cases at the end, once you have the main algorithm idea. You should be focused on the “typical” (not edge) case.

Problem 1.2 – Maximum Subarray Sum

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

Work through generating some examples, and then we’ll go over it together!

Problem 1.2 – Maximum Subarray Sum

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

Problem 1.2 – Maximum Subarray Sum

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

3. Come Up with a Baseline

Inefficient (non Divide and Conquer) First Attempt

• Review: In a time-constrained setting (like a technical interview or an exam) you often want a “baseline” algorithm. This should be an algorithm that you can implement and will give you the right answer, even if it might be slow.

​

• When you’re pretty sure you want to use a Divide and Conquer algorithm, this step is very important! You need a (brute force) non Divide and Conquer baseline (with a quick runtime analysis) so you can see whether all the recursive steps of your Divide and Conquer algo are actually saving you any time!

Problem 1.3 – Maximum Subarray Sum

What is the first algorithm that comes to mind for the problem? What would it’s running-time be? (Don’t try to do divide and conquer yet).

​

Problem 1.3 – Maximum Subarray Sum

Problem 1.3 – Maximum Subarray Sum

Problem 1.3 – Maximum Subarray Sum

function BetterBaseline(A[1..n])

bestSum ← −∞

for i from 1 to n do // i represents start index

sum ← 0

for j from i to n do // j represents end index

sum += A[j]

if sum > bestSum then

bestSum ← sum

if bestSum < 0 then // handle all negative entries case

return 0 // empty subarray must be best here

return bestSum

Problem 1.3 – Maximum Subarray Sum

function BetterBaseline(A[1..n])

bestSum ← −∞

for i from 1 to n do // i represents start index

sum ← 0

for j from i to n do // j represents end index

sum += A[j]

if sum > bestSum then

bestSum ← sum

if bestSum < 0 then // handle all negative entries case

return 0 // empty subarray must be best here

return bestSum

4. Brainstorm and Analyze �Possible Algorithms

Think about How to Divide and Conquer

• Questions to help you brainstorm out your Divide and Conquer algo:
• How do you want to split up the problem?
• What is returned from the recursive calls? (hint: look back at part 1)
• Imagine you have the answers from those recursive calls; �what is there still to handle?

​

• When you have time, it’s a good idea to try to run through your idea with some of the examples you came up with earlier, and see whether you get the correct output (especially as you try to transition from your brainstorming to formalizing your algorithm)

Problem 1.4 – Maximum Subarray Sum

For each call SubarraySumDC(A[1..n]) answer these questions:

How do you want to split up the problem?

​

​

​

What is returned from the recursive calls?

​

​

​

Imagine you have the answers from those recursive calls; what is there still to handle?

​

Problem 1.4 – Maximum Subarray Sum

For each call SubarraySumDC(A[1..n]) answer these questions:

How do you want to split up the problem?

​

​

​

What is returned from the recursive calls?

​

​

​

Imagine you have the answers from those recursive calls; what is there still to handle?

​

Let’s just split the array in half! Make two recursive calls, one for each half (we don’t know where the subarray is, so we’ll have to make both).

Problem 1.4 – Maximum Subarray Sum

For each call SubarraySumDC(A[1..n]) answer these questions:

How do you want to split up the problem?

​

​

​

What is returned from the recursive calls?

​

​

​

Imagine you have the answers from those recursive calls; what is there still to handle?

​

Let’s just split the array in half! Make two recursive calls, one for each half (we don’t know where the subarray is, so we’ll have to make both).

Each recursive call will return the sum of the largest subarray among half the elements, either 1,…n/2 or n/2+1,…n.

Problem 1.4 – Maximum Subarray Sum

For each call SubarraySumDC(A[1..n]) answer these questions:

How do you want to split up the problem?

​

​

​

What is returned from the recursive calls?

​

​

​

Imagine you have the answers from those recursive calls; what is there still to handle?

​

Let’s just split the array in half! Make two recursive calls, one for each half (we don’t know where the subarray is, so we’ll have to make both).

Each recursive call will return the sum of the largest subarray among half the elements, either 1,…n/2 or n/2+1,…n.

If the subarray “crosses” from one side to the other (i.e., includes both n/2 and n/2+1), it hasn’t been checked yet. We still need to discover and check those.

5. Write an Algorithm

Translate the brainstorm into an algorithm!

• We need to take those ideas we were just noodling on and write them into an algorithm!
• We can start with formalizing our ideas from earlier, but then we still need to figure out how to deal with those subarrays that cross from one half to the other…

Translate the brainstorm into an algorithm!

Translate the brainstorm into an algorithm!

Problem 1.5 – Maximum Subarray Sum

On whiteboard (see solutions)

6. Show Your Algorithm is Correct

Problem 1.6 – Maximum Subarray Sum

Write a proof of correctness.

Work on this proof with the people around you, and then we’ll go over it together!

Problem 1.6 – Maximum Subarray Sum

Problem 1.6 – Maximum Subarray Sum

7. Optimize and Analyze the Run Time

Problem 1.7 – Maximum Subarray Sum

Write the big-O of your code and justify the running time with a few sentences.

Problem 1.7 – Maximum Subarray Sum

Write the big-O of your code and justify the running time with a few sentences.

That’s All, Folks!

Thanks for coming to section this week!

Any questions?

​