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 2Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!