Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter5 [2018/03/13 03:38] – [5.1 – A First Recurrence: The Mergesort Algorithm] bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter5 [2018/03/13 03:54] (current) – bairdc
@@ Line 8: / Line 8: @@
 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.