Application of divide and conquer algorithms

divide and conquer algorithm definition and divide and conquer algorithm example problems
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Divide-and- conquer Douglas Wilhelm Harder, M.Math. LEL algorithms Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Divide-and-conquer algorithms 2 Divide-and-conquer algorithms We have seen four divide-and-conquer algorithms: – Binary search – Depth-first tree traversals – Merge sort – Quick sort The steps are: – A larger problem is broken up into smaller problems – The smaller problems are recursively – The results are combined together again into a solutionDivide-and-conquer algorithms 3 Divide-and-conquer algorithms For example, merge sort: – Divide a list of size n into b = 2 sub-lists of size n/2 entries – Each sub-list is sorted recursively – The two sorted lists are merged into a single sorted listDivide-and-conquer algorithms 4 Divide-and-conquer algorithms More formally, we will consider only those algorithms which: – Divide a problem into b sub-problems, each approximately of size n/b • Up to now, b = 2 – Solve a ≥ 1 of those sub-problems recursively • Merge sort and tree traversals solved a = 2 of them • Binary search solves a = 1 of them – Combine the solutions to the sub-problems to get a solution to the overall problemDivide-and-conquer algorithms 5 Divide-and-conquer algorithms With the three problems we have already looked at we have looked at two possible cases for b = 2: Merge sort b = 2 a = 2 Depth-first traversal b = 2 a = 2 Binary search b = 2 a = 1 Problem: the first two have different run times: Merge sortQ(n ln(n) ) Depth-first traversalQ(n)Divide-and-conquer algorithms 6 Divide-and-conquer algorithms Thus, just using a divide-and-conquer algorithm does not solely determine the run time We must also consider – The effort required to divide the problem into two sub-problems – The effort required to combine the two solutions to the sub-problemsDivide-and-conquer algorithms 7 Divide-and-conquer algorithms For merge sort: – Division is quick (find the middle): Q(1) – Merging the two sorted lists into a single list is a Q(n) problem For a depth-first tree traversal: – Division is also quick: Q(1) – A return-from-function is preformed at the end which is Q(1) For quick sort (assuming division into two): – Dividing is slow: Q(n) – Once both sub-problems are sorted, we are finished: Q(1)Divide-and-conquer algorithms 8 Divide-and-conquer algorithms Thus, we are able to write the expression as follows: – Binary search: 1 n 1   n Q(ln(n))  T(n)  TΘ(1) n 1   2   – Depth-first traversal: 1 n 1  Q(n)  n  T(n)  2TΘ(1) n 1   2   – Merge/quick sort: Q(n ln(n)) 1 n 1   n  T(n)  2TΘ(n) n 1   2   In general, we will assume the work done combined work is of the k form O(n )Divide-and-conquer algorithms 9 Divide-and-conquer algorithms Thus, for a general divide-and-conquer algorithm which: – Divides the problem into b sub-problems – Recursively solves a of those sub-problems k – Requires O(n ) work at each step requires has a run time 1 n 1   n  T(n) k  a TOn n 1   b   Note: we assume a problem of size n = 1 is solved...Divide-and-conquer algorithms 10 Divide-and-conquer algorithms Before we solve the general case, let us look at some more complex examples: – Searching an ordered matrix – Integer multiplication (Karatsuba algorithm) – Matrix multiplicationDivide-and-conquer algorithms 11 Searching an ordered matrix Consider an n × n matrix where each row and column is linearly ordered; for example: – How can we determine if 19 is in the matrix?Divide-and-conquer algorithms 12 Searching an ordered matrix Consider the following search for 19: – Search across until a 19 i,j + 1 – Alternate between • Searching down until a 19 i,j • Searching back until a 19 i,j This requires us to check at most 3n entries: O(n)Divide-and-conquer algorithms 13 Searching an ordered matrix Can we do better than O(n)? Logically, no: any number could appear in up to n positions, each of which must be checked – Never-the-less: let’s generalize checking the middle entryDivide-and-conquer algorithms 14 Searching an ordered matrix 17 19, and therefore, we can only exclude the top-left sub-matrix:Divide-and-conquer algorithms 15 Searching an ordered matrix Thus, we must recursively search three of the four sub-matrices – Each sub-matrix is approximately n/2 × n/2Divide-and-conquer algorithms 16 Searching an ordered matrix If the number we are searching for was less than the middle element, e.g., 9, we would have to search three different squaresDivide-and-conquer algorithms 17 Searching an ordered matrix Thus, the recurrence relation must be 1 n 1   n  T(n)  3TΘ(1) n 1   2   because – T(n) is the time to search a matrix of size n × n – The matrix is divided into 4 sub-matrices of size n/2 × n/2 – Search 3 of those sub-matrices – At each step, we only need compare the middle element: Q(1)Divide-and-conquer algorithms 18 Searching an ordered matrix We can solve the recurrence relationship 1 n 1   n  T(n)  3TΘ(1) n 1   2   using Maple: rsolve( T(n) = 3T(n/2) + 1, T(1) = 1, T(n) ); log (3) 3 2 1 n 2 2 evalf( log2( 3 ) ); 1.584962501Divide-and-conquer algorithms 19 Searching an ordered matrix 1.585 Therefore, this search is approximately O(n ), which is significantly worse than a linear search:Divide-and-conquer algorithms 20 Searching an ordered matrix Note that it is T(n) = 3T(n/2) + Q(1) and not T(n) = 3T(n/4) + Q(1) We are breaking the n × n matrix into four (n/2) × (n/2) matrices 2 If N = n , then we could write T(N) = 3T(N/4) + Q(1)