Courses

# Algorithms - Divide and Conquer Notes | EduRev

## : Algorithms - Divide and Conquer Notes | EduRev

``` Page 1

CSE 421
Algorithms:
Divide and Conquer

Larry Ruzzo

Thanks to Paul Beame, Kevin Wayne for some slides

Page 2

CSE 421
Algorithms:
Divide and Conquer

Larry Ruzzo

Thanks to Paul Beame, Kevin Wayne for some slides

4

algorithm design paradigms: divide and conquer
Outline:

General Idea

Review of Merge Sort

Why does it work?

Importance of balance

Importance of super-linear growth

Some interesting applications

Closest points

Integer Multiplication

Finding & Solving Recurrences

Page 3

CSE 421
Algorithms:
Divide and Conquer

Larry Ruzzo

Thanks to Paul Beame, Kevin Wayne for some slides

4

algorithm design paradigms: divide and conquer
Outline:

General Idea

Review of Merge Sort

Why does it work?

Importance of balance

Importance of super-linear growth

Some interesting applications

Closest points

Integer Multiplication

Finding & Solving Recurrences

5

algorithm design techniques
Divide & Conquer

Reduce problem to one or more sub-problems of
the same type

Typically, each sub-problem is at most a constant
fraction of the size of the original problem

Subproblems typically disjoint

Often gives signi?cant, usually polynomial, speedup

Examples:

Mergesort, Binary Search, Strassen’s Algorithm,
Quicksort (roughly)

Page 4

CSE 421
Algorithms:
Divide and Conquer

Larry Ruzzo

Thanks to Paul Beame, Kevin Wayne for some slides

4

algorithm design paradigms: divide and conquer
Outline:

General Idea

Review of Merge Sort

Why does it work?

Importance of balance

Importance of super-linear growth

Some interesting applications

Closest points

Integer Multiplication

Finding & Solving Recurrences

5

algorithm design techniques
Divide & Conquer

Reduce problem to one or more sub-problems of
the same type

Typically, each sub-problem is at most a constant
fraction of the size of the original problem

Subproblems typically disjoint

Often gives signi?cant, usually polynomial, speedup

Examples:

Mergesort, Binary Search, Strassen’s Algorithm,
Quicksort (roughly)

merge sort

MS(A: array[1..n]) returns array[1..n] {

If(n=1) return A;

New U:array[1:n/2] = MS(A[1..n/2]);

New L:array[1:n/2] = MS(A[n/2+1..n]);

Return(Merge(U,L));

}

Merge(U,L: array[1..n]) {

New C: array[1..2n];

a=1; b=1;

For i = 1 to 2n

C[i] = “smaller of U[a], L[b] and correspondingly a++ or b++”;

Return C;

}

6

A U C
L

split     sort    merge

Page 5

CSE 421
Algorithms:
Divide and Conquer

Larry Ruzzo

Thanks to Paul Beame, Kevin Wayne for some slides

4

algorithm design paradigms: divide and conquer
Outline:

General Idea

Review of Merge Sort

Why does it work?

Importance of balance

Importance of super-linear growth

Some interesting applications

Closest points

Integer Multiplication

Finding & Solving Recurrences

5

algorithm design techniques
Divide & Conquer

Reduce problem to one or more sub-problems of
the same type

Typically, each sub-problem is at most a constant
fraction of the size of the original problem

Subproblems typically disjoint

Often gives signi?cant, usually polynomial, speedup

Examples:

Mergesort, Binary Search, Strassen’s Algorithm,
Quicksort (roughly)

merge sort

MS(A: array[1..n]) returns array[1..n] {

If(n=1) return A;

New U:array[1:n/2] = MS(A[1..n/2]);

New L:array[1:n/2] = MS(A[n/2+1..n]);

Return(Merge(U,L));

}

Merge(U,L: array[1..n]) {

New C: array[1..2n];

a=1; b=1;

For i = 1 to 2n

C[i] = “smaller of U[a], L[b] and correspondingly a++ or b++”;

Return C;

}

6

A U C
L

split     sort    merge

why balanced subdivision?
Alternative "divide & conquer" algorithm:

Sort n-1

Sort last 1

Merge them

T(n) = T(n-1)+T(1)+3n   for n = 2

T(1) = 0

Solution: 3n + 3(n-1) + 3(n-2) … =  T(n
2
)

7

```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!