[[courses:cs211:winter2018:journals:holmesr:section_5.0]]
Trace: • section_1.1 • ch2 • chapter3 • preface • chapter2 • section_6.1 • ch2 • chapter_5 • chapter4 • chapter7
Show page
Recent ChangesSitemap

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2018:journals:holmesr:section_5.0 [2018/03/14 03:49] – holmesrcourses:cs211:winter2018:journals:holmesr:section_5.0 [2018/03/14 03:50] (current) – holmesr
Line 1: Line 1:
 ====== Chapter 5 Divide and Conquer algorithms ====== ====== Chapter 5 Divide and Conquer algorithms ======
-====== Section 5.1 The Mergesort Algorithm ======+===== Section 5.1 The Mergesort Algorithm =====
  
 The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, it will "bottom out" at a base case of constant size.  The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, it will "bottom out" at a base case of constant size. 
Line 10: Line 10:
 There are also methods using substitution and partial substitution to solve for the running time but these seem to me to be unhelpful unless you already have a solid guess for the running time. Even in the case that you have a solid guess for running time though, it is still a guess and more likely to lead you down the wrong path than unrolling the recursion, so why not just unroll it from the start in order to save yourself time, frustration and guesswork? These two substitution sections at the end are my main issue with the section 5.1 since they seem to add now value, at least in my mind. Maybe I simply don't understand them though. There are also methods using substitution and partial substitution to solve for the running time but these seem to me to be unhelpful unless you already have a solid guess for the running time. Even in the case that you have a solid guess for running time though, it is still a guess and more likely to lead you down the wrong path than unrolling the recursion, so why not just unroll it from the start in order to save yourself time, frustration and guesswork? These two substitution sections at the end are my main issue with the section 5.1 since they seem to add now value, at least in my mind. Maybe I simply don't understand them though.
  
-====== Section 5.2 Further Recurrence Relations ======+===== Section 5.2 Further Recurrence Relations =====
  
 This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n) <= qT(n/2) + cn when n > 2.  This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n) <= qT(n/2) + cn when n > 2. 
Line 23: Line 23:
  
 Finally, we can consider what happens in the case that the algorithm "divides up the input into two different pieces of size n/2, solves the subproblems by recursion, and then combines the two into an overall solution, spending quadratic time instead for the initial division and final recombining." This is different from the problems such as mergesort since it takes quadratic time for the division and recombining instead of linear. So the problems take this form: T(n) <= 2T(n/2) + cn<sup>2</sup>. Instinctively, one would like to say that this should be bounded by O(n<sup>2</sup> log n) however it is actually bounded by O(n<sup>2</sup>) due to how quickly n<sup>2</sup> decreases as it is replaced with n/(2<sup>j</sup>) Finally, we can consider what happens in the case that the algorithm "divides up the input into two different pieces of size n/2, solves the subproblems by recursion, and then combines the two into an overall solution, spending quadratic time instead for the initial division and final recombining." This is different from the problems such as mergesort since it takes quadratic time for the division and recombining instead of linear. So the problems take this form: T(n) <= 2T(n/2) + cn<sup>2</sup>. Instinctively, one would like to say that this should be bounded by O(n<sup>2</sup> log n) however it is actually bounded by O(n<sup>2</sup>) due to how quickly n<sup>2</sup> decreases as it is replaced with n/(2<sup>j</sup>)
 +
 +===== Section 5.3 Counting Inversions =====
 +
 +The motivation for this type of problem is based in the analysis of a set of rankings compared to a different set of rankings of the same items. A way to compare these sets of ordered items is to look at how many pairs are "out of order" from one ranking to another. An inversion occurs when indices i<j but a<sub>i</sub>>a<sub>j</sub>. 
 +
 +Looking at every pair of numbers would require O(n<sup>2</sup>)time, so to find the O(n log n) solution, we must find one that does not even have to evaluate every value. This solution is to divide the list of numbers into two half-sized sublists then counting the number of inversions in each half and finally counting inversions between the two halves. The merge-and-count algorithm is the solution that hinges on this principle. 
 +
 +Merge-and-count works by maintaining pointers to the front of each sublist and removing the lesser one from its sublist when it is added to what will become the sorted list. The algorithm must also count the number of inversions in addition to ordering the list. It does this by increasing the count of inversions by whatever the remaining size of the first subset of rankings is. This operation counts a possibly large number of inversions in constant time. Thus, O(n log n) running time.
 +
 +I found this chapter fairly straightforward to understand.
courses/cs211/winter2018/journals/holmesr/section_5.0.1520999378.txt.gz · Last modified: by holmesr
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0