Courses

# Divide & Conquer - PPT Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : Divide & Conquer - PPT Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

Divide and Conquer
Andreas Klappenecker
[based on slides by Prof. Welch]
Page 2

Divide and Conquer
Andreas Klappenecker
[based on slides by Prof. Welch]
• An important general technique for
designing algorithms:
• divide problem into subproblems
• recursively solve subproblems
• combine solutions to subproblems to get
solution to original problem
• Use recurrences to analyze the
running time of such algorithms
Page 3

Divide and Conquer
Andreas Klappenecker
[based on slides by Prof. Welch]
• An important general technique for
designing algorithms:
• divide problem into subproblems
• recursively solve subproblems
• combine solutions to subproblems to get
solution to original problem
• Use recurrences to analyze the
running time of such algorithms
Mergesort
Page 4

Divide and Conquer
Andreas Klappenecker
[based on slides by Prof. Welch]
• An important general technique for
designing algorithms:
• divide problem into subproblems
• recursively solve subproblems
• combine solutions to subproblems to get
solution to original problem
• Use recurrences to analyze the
running time of such algorithms
Mergesort
Example: Mergesort
• DIVIDE the input sequence in half
• RECURSIVELY sort the two halves
• basis of the recursion is sequence with 1
key
• COMBINE the two sorted subsequences
by merging them
Page 5

Divide and Conquer
Andreas Klappenecker
[based on slides by Prof. Welch]
• An important general technique for
designing algorithms:
• divide problem into subproblems
• recursively solve subproblems
• combine solutions to subproblems to get
solution to original problem
• Use recurrences to analyze the
running time of such algorithms
Mergesort
Example: Mergesort
• DIVIDE the input sequence in half
• RECURSIVELY sort the two halves
• basis of the recursion is sequence with 1
key
• COMBINE the two sorted subsequences
by merging them
Mergesort Example
1 3 2 4 2 5 6 6
2 6 4 5 1 2 6 3
5 2 6 4 1 3 6 2
5 2 6 4
2 5 6 4
1 3
1 3
6 2
6 2
5 6 2 4
5 6 2 1 4 3 6 2
1 3 6 2
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;