This chapter provides knowledge of divide and conquer. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Divide-and-Conquer 3/29/14 21:29 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Divide-and-Conquer 7 2 ⏐ 9 4 → 2 4 7 9 7 ⏐ 2 → 2 7 7→7 © 2014 Goodrich, Tamassia, Goldwasser 2→2 Divide-and-Conquer 9 ⏐ 4 → 4 9 9→9 4→4 1 Divide-and-Conquer ! Divide-and conquer is a general algorithm design paradigm: n n n Divide: divide the input data S in two or more disjoint subsets S1, S2, Conquer: solve the subproblems recursively Combine: combine the solutions for S1, S2, , into a solution for S ! The base case for the recursion are subproblems of constant size ! Analysis can be done using recurrence equations © 2014 Goodrich, Tamassia, Goldwasser Divide-and-Conquer 2 1 Divide-and-Conquer 3/29/14 21:29 Merge-Sort Review ! Merge-sort on an input sequence S with n elements consists of three steps: n n n Divide: partition S into two sequences S1 and S2 of about n/2 elements each Conquer: recursively sort S1 and S2 Combine: merge S1 and S2 into a unique sorted sequence © 2014 Goodrich, Tamassia, Goldwasser Algorithm mergeSort(S) Input sequence S with n elements Output sequence S sorted according to C if () > 1 (S1, S2) ← partition(S, n/2) mergeSort(S1) mergeSort(S2) S ← merge(S1, S2) Divide-and-Conquer 3 Recurrence Equation Analysis ! The conquer step of merge-sort consists of merging two sorted ! ! sequences, each with n/2 elements and implemented by means of a doubly linked list, takes at most bn steps, for some constant b. Likewise, the basis case (n b. ≤ cn log 2 n ! So, T(n) is O(n log2 n). ! In general, to use this method, you need to have a good guess and you need to be good at induction proofs. © 2014 Goodrich, Tamassia, Goldwasser Divide-and-Conquer 8 4 Divide-and-Conquer 3/29/14 21:29 Master Method (Appendix) ! Many divide-and-conquer recurrence equations have the form: c ⎧ T (n) = ⎨ ⎩ aT (n / b)
