Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter5 [2018/03/12 23:40] – created bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter5 [2018/03/13 03:54] (current) – bairdc
@@ Line 4: / Line 4: @@
 ===== 5.1 – A First Recurrence: The Mergesort Algorithm =====
+In the Mergesort algorithm, we divide the input into 2 pieces of equal size and solve the 2 subproblems. After solving the 2 halves by recursion, we combing the 2 results into an overall solution, spending linear time for everything. The recurrence relation for Mergesort is T(n) <= T([n/2]) + T([n/2]) + cn. To solve such a recurrence you can either unroll the recursion or guess for the solution, substitute it into the recurrence relation, and then check and see if it works. Unrolling seems to be the most intuitive. Unrolling the recursion, we get that Mergesort takes O(nlogn).
+Overall this section was very readable and interesting. I'd give it a 9/10 for both.
+===== 5.2 – Further Recurrence Relations =====
+Mergesort creates recursive calls on q subproblems of size n/2 each and then combines them in O(n) time. For q > 2 subproblems, the functions bounded by O(n^logq). For 1 subproblem, the function is bounded by O(n). The summations mostly make sense, but I need to look at them a bit more in depth to make sense of them. Recurrence relations are still a bit tricky for me right now.
+Overall I'd give this section a 6/10 on readability and a 7/10 on interestingness.
+===== 5.3 – Counting Inversions =====
+The inversion counting problem tends to arise in comparing two rankings. Any two indices i < j form an inversion if ai > aj. Or, in other words, if elements ai and aj are "out of order". Brute force can solve this issue in O(n^2), but we can do better with MergeAnd Count and SortAndCount. These combine to run in O(nlogn) time.
+<code>
+Merge-and-Count(A,B):
+  i=0
+  j=0
+  inversions = 0
+  output = []
+  while i < A.size and j < B.size:
+    output.append( min(A[i], B[j]) )
+    if B[j] < A[i]:
+      inversions += A.size – i
+    update i or j
+  Append the remainder of the non-exhausted list to
+  the output
+  return inversions and output
+Sort-and-Count(L)
+  if list L has one element
+    return 0 and the list L
+  Divide the list into two halves A and B
+  (iA, A) = Sort-and-Count(A)
+  (iB, B) = Sort-and-Count(B)
+  (i, L) = Merge-and-Count(A, B)
+  total_inversions = iA + iB + i
+  return total_inversions and the sorted list L
+</code>
+I'd give this section a 9/10 on readability and interestingness.