Divide and Conquer: A Strategy for Problem Solving
Divide-and-conquer is a powerful problem-solving technique in Computer Science where a large problem is divided into smaller sub-problems, conquered individually, and then combined to solve the original problem. Through three steps - Divide, Conquer, and Combine - complex problems can be efficiently tackled. Recursive solutions are commonly employed, as demonstrated in examples like sorting and sum computation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Divide-and-conquer and recursion Divide-and-conquer o A useful strategy for solving large problems o Divide a large (original) problem into smaller (and simpler) sub-problems, then conquer the sub- problems, and finally solve the original large problem by combining the solutions of the smaller sub-problems. o Three steps: 1. Divide: divide the problem into smaller sub-problems 2. Conquer: solve sub-problems 3. Combine: Combine the solutions of sub-problems to get the solution for the original problem o Divide and conquer is probably the most used problem solving technique in Computer Science and it has been applied in many contexts. Example applications of the divide-and-conquer technique: Module design in software engineering, software stacks (full stack developers), layered architecture.
Divide-and-Conquer and Recursion Divide-and-conquer can lead to a recursive solution for a problem 1. Divide: divide the problem into smaller sub-problems; sub-problems must be the same as the original problem (but smaller size). From coding s perspective, sub-problems can be solved by making the same function call with different parameters. 2. Conquer: solve sub-problems by recursive calls 3. Combine: Combine the solutions of sub-problems (recursive calls) and whatever logic needed to get the solution for the original problem Example1: Sort N numbers using insertion sort o Divide: one sub-problem - Sort (the first or last) N-1 numbers o Conquer: make a recursive call to sort the last N-1 numbers o Combine: Insert the first number into the sorted N-1 numbers to make a sorted N numbers.
More examples Example 2: Merge Sort of (N numbers) o Divide: two sub-problems: (1) Sort the first N/2 numbers, (2) Sort the last N/2 integers o Conquer: sorting N/2 numbers can be achieved by a recursive call. o Combine: Merge the two sorted lists into one sorted list. Example 3: Compute the sum of N numbers (in a vector) o Divide: one sub-problem: compute the sum of first N-1 numbers o Conquer: Compute the sum of the N-1 numbers by a recursive call o Combine: Adding last number to the result of the recursive call (sum of the first N-1 numbers) yields the sum of the N Numbers.
Writing recursive routines with divide-and-conquer 1) logically understand (1) how the problem can be divided into the same kind of problems of smaller sizes and (2) how the solutions of the smaller problems can be used to form the solution of the original problem (as the examples in the previous slides)
Writing recursive routines with divide-and-conquer 2) formulate the solution of the problem into a routine with proper parameters. The key is to make sure that both the original problem and the smaller problems can both be formulated with the same routine prototype Example: template <class iterator> typename iterator_traits<iterator>::value_type sum(iterator beg, iterator end) Sub problem: sum(++beg, end) template<class T> void insertion_sort(vector<T>& v, int b, int e) Sub problem: insert_sort(v, b+1, e);
Writing recursive routines with divide-and-conquer 3) write the base case. This is often the easy cases when the problem size is 0 or 1. Example: typename iterator_traits<iterator>::value_type sum(iterator beg, iterator end) If (beg == end) return 0; template<class T> void insertion_sort(vector<T>& v, int b, int e) If (b >=e-1) return;
Writing recursive routines with divide-and-conquer 4) write the recursive case this is logic to combine the solutions for smaller problems to form solution for the original problem. Sometimes it is simple: typename iterator_traits<iterator>::value_type sum(iterator beg, iterator end) If (beg == end) return 0; return *beg + sum(++beg, end);
Writing recursive routines with divide-and-conquer Step 4: write the recursive case this is logic to combine the solutions for smaller problems to form solution for the original problem. Sometimes it is longer (still easier then sorting the whole thing) template<class T> void insertion_sort(vector<T>& v, int b, int e) If (b >=e) return; Insertion_sort(v, b+1, e); T t = v[b]; int j = b+1; while ((t > v[j]) && (j <= e) {v[j-1] = v[j]; j++;} v[j-1] = t;
Writing recursive routines Putting routine prototype, base case, recursive case together to form a complete recursive routine. See examples in examples/recursion/recursion.cpp.
Thinking in recursion Establish the base case (degenerated case): it is usually trivial. The main part (recursive case): if we can solve the problem of size N-1, can we use that to solve the problem of size N? oIf yes: Find the right routine prototype Base case Recursive case
Recursion and proof by induction Mathematic induction (useful tool for theorem proofing) o First prove a base case (N=1) Show the theorem is true for some small degenerate values o Next assume an inductive hypothesis Assume the theorem is true for all cases up to some limit (N=k) o Then prove that the theorem holds for the next value (N=k+1) Recursion o Base case: we know how to solve the problem for the base case (N=0 or 1). o Recursive case: Assume that we can solve the problem for N=k, we can solve the problem for N=k+1. Recursion is basically applying induction to problem solving!!
Extra points No. 5: Number puzzle You are given N numbers, you want to find whether these N numbers can form an expression using +, -, *, / operators that evaluates to result. o Example, give four numbers 6, 3, 1, 1 (N=4), result = 24. o Answer: Yes, expression: 1*(1+3)*6 = 24 o Another example: given 4 numbers 2, 2, 2, 2, result = 24 o Answer: No.
Extra points No. 5 : number puzzle You are given N numbers, you want to find whether these N numbers can form an expression using +, -, *, / operators that evaluates to result. Thinking recursion: o Base case, when N=1, you are give one number X to make result. How to do it?
Extra points No. 5 : number puzzle You are given N numbers, you want to find whether these N numbers can form an expression using +, -, *, / operators that evaluates to result. Thinking recursion: o Base case, when N=1, you are give one number v[0] to make result. o if (v[0] == result) return true o else return false;
Extra points No. 5 : number puzzle You are given N numbers, you want to find whether these N numbers can form an expression using +, -, *, / operators that evaluates to result. Thinking recursion: o Recursive case: Assume that given N-1 numbers, we know how to decide whether these N- 1 numbers can form the expression that evaluates to result, can we solve the problem for N number? Function prototype: bool computeexp(int n, vector<int> v, int res) /* if the n items in v can make an expression that evaluates to res, return true, else return false. */
Extra points No. 5 : number puzzle You are given N numbers, you want to find whether these N numbers can form an expression using +, -, *, / operators that evaluates to result. Thinking recursion: o Recursive case: computeexp(n-1, v, res) will give you a true/false answer about whether the n-1 numbers in v can evaluate to res. Can we solve the problem with n numbers? We can reduce the N numbers problem to N-1numbers problem by picking two numbers and applying +, -, *, / on the two numbers (to make one number) and keep the rest N-2 numbers: the problem is now reduced to whether these N-1 Numbers can evaluate to res To cover all possible cases, the program must consider all pairs of numbers from the N numbers: there are N(N-1) pairs, each pair would require a recursive call.
bool computeexp(int n, vector<int> v, int res) { if (n== 1) { // base case } for (int i=0; i<n; i++) { for (int k=0; k<n; k++) { if (i == k) continue; // only one number // make a vector w of with all items of v except v[i] and v[k], add v[i] + v[k] to w if (computeexp(n-1, w, res)) return true; // make a vector w of with all items of v except v[i] and v[k], add v[k] + v[i] to w if (computeexp(n-1, w, res)) return true; // make a vector w of with all items of v except v[i] and v[k], add v[i] - v[k] to w if (computeexp(n-1, w, res)) return true; // make a vector w of with all items of v except v[i] and v[k], add v[k] - v[i] to w if (computeexp(n-1, w, res)) return true; // . Deal with * and / } } }
Challenge problem: number puzzle Print out the expression to get the result oYou can associate an expression (string type) with each number (the expression evaluates to the number). You can print the expression when a solution is found. oThe expression is in the parameter to the recursive function. bool computeexp(int n, vector<int> v, vector<string> exp, int res)
