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] 
Divide and Conquer Paradigm 
• 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] 
Divide and Conquer Paradigm 
• 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] 
Divide and Conquer Paradigm 
• 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] 
Divide and Conquer Paradigm 
• 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 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

ppt

,

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

,

mock tests for examination

,

video lectures

,

Objective type Questions

,

Important questions

,

Sample Paper

,

Free

,

pdf

,

Exam

,

past year papers

,

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

,

Previous Year Questions with Solutions

,

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

,

Viva Questions

,

MCQs

,

Extra Questions

,

practice quizzes

,

Semester Notes

,

Summary

,

shortcuts and tricks

,

study material

;