Differences

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

--- courses:cs211:winter2018:journals:lesherr:home:chapter5 [2018/03/11 16:32] – created lesherr
+++ courses:cs211:winter2018:journals:lesherr:home:chapter5 [2018/03/11 17:14] (current) – [Section 3: Counting Inversions] lesherr
@@ Line 1: / Line 1: @@
 ====== Chapter 5: Divide and Conquer ======
 ===== Section 1: A First Recurrence: The Mergesort Algorithm =====
+'The Mergesort Algorithm sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive halves.' The abstract behavioral template for many common divide-and-conquer algorithms is this: 'Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.' This type of recursive methodology requires a base case, having it 'bottom out' on inputs of some constant size. In the case of Mergesort, once input has been reduced to size 2, we stop the recursive process and sort the two elements in one comparison. For each recursive algorithm, there is a recursive relation to describe its processes. It follows the formula T(n) = cT(k) + O(l), where c is the number of subproblems, k is the factor by which the input size decreases, and l is the cost of recombining the subproblems into a single problem. The two basic ways to go about solving a recurrence are: 1) unrolling the recursion, accounting for the running time of across the first few levels and identifying a pattern of the recursion, and then summing the run times of all the levels to find the total run time, and 2) Start with a guess for the solution, substitute into the recurrence relation, and check that it works. For 1), we first analyze the first few levels, identify a pattern, and then sum over all levels of recursion. 'Any function T(-) satisfying T(n) <= 2T(n/2) + O(n) is bounded by O(nlogn), when n > 1. For 2) we first take our guess for what the run time is, plug it into the recurrence relation, and check to see if completes the induction argument. There is also a weaker form of substitution when we are unsure of the whole run-time of our guess. This section was very easy to understand having talked about it in class, and given prior experience with the Mergesort Algorithm. I would give it a 9/10.
 ===== Section 2: Further Recurrence Relations =====
+The Mergesort algorithm serves as a very good example of recursion that we can use to generalize for a much larger class of divide-and-conquer algorithms. These algorithms follow the same pattern of splitting the initial sample size into smaller samples of size n/2, however we want to look at cases where the number of smaller sizes is not binary, (i.e. q > 2). Analyzing the first few levels, we see that the total work per level is increasing as we proceed through the recursion. Identifying a pattern, we see that the total work performed at level k is q^k(cn/(2^k), which is equivalent to (q/2)^k*cn. Summing this over all levels of recursion, we see that the total run time for an algorithm of this setup is O(n^(logq)). Any algorithm that follows the recurrence relation of T(n) = qT(n/2) + O(n) with q > 2 will have a run time of the form O(n^(logq)). Considering an algorithm that follows that form with q = 1, we see that the work per level is actually decreasing as we proceed through the recursion. The pattern for the cost per level l is cn/2^l, and thus the sum of the total work of the algorithm is O(n). Any function with that form will always be bounded by O(n). Thus from this analysis, we see that the value of q in the algorithm has a major effect on the total run time. When q = 1, the run time is linear, when q = 2, the run time is O(nlogn), when q >2, the run time is O(n^(logq)). A related recurrence to those of which we have been looking at is T(n) = 2T(n/2) + O(n^2). This recurrence follows the structure of: divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining. Analyzing the first few levels, we see that the total amount of work per level is decreasing, as opposed to mergesort where the total work stays the same per level. Identifying a pattern, we see the total work per level l is cn^2/2l. Summing the total work over all levels, we find that the total run time is O(n^2). The beginning of this section was easy to follow having studied it in class and worked on the problem set. The second part was a bit more confusing, with regards to the different algorithm. I would give this section a 6/10.
 ===== Section 3: Counting Inversions =====
+In this section, we consider a problem that arises in the analysis of rankings. An example of this is collaborative filtering, where sites try to match your preferences with those of other people to find people with similar tastes, so that they can recommend new things that you might like. A major issue in applications that use this is comparing two rankings to find how similar two people's rankings are. A natural way to quantify how different two rankings are is by counting the number of inversions there are between the two, or the number of times a pair of elements is out of order. For a sequence in ascending order, there are no inversions, but for a sequence in descending order, there are n choose 2 inversions, since every pair is an inversion. A brute force algorithm to calculate the number of inversions would take O(n^2) time, looking at every pair of elements. The following algorithm can achieve this calculation in O(nlogn) time.
+Merge-and-Count(A,B)
+     Maintain a current pointer into each list, initialized to point to the front element
+     Maintain a variable Count for the number of inversions, initialized to 0
+     While both lists are nonempty
+          let ai and bj be the elements pointed to by the Current pointer
+          Append the smaller of these two to the output list
+          If bj is the smaller element
+               Increment Count by the number of elements remaining in A
+          Advance the Current pointer in the list from which the smaller element was selected
+     Once one list is empty, append the remainder of the other list to the output
+     Return Count and the merged list
+Sort-and-Count(L)
+     If the list has one element then there are no inversions
+     Else
+          Divide the list into two halves:
+               A contains the first [n/2] elements
+               B contains the remaining [n/2] elements
+               (rA, A) = sort-and-count(A)
+               (rB, B) = sort-and-count(B)
+               (r, L) = merge-and-count(A,B)
+     return r = rA + rB + r, and the sorted list L
+'The Sort-and-count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(nlogn) time for a list with n elements.' This section was more difficult to understand, and hopefully will be made clearer in class. I would give it a 5/10.