Differences

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

--- courses:cs211:winter2018:journals:donohuem:chapter5 [2018/03/12 21:00] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:chapter5 [2018/03/12 21:39] (current) – [5.3 Counting Inversions] donohuem
@@ Line 8: / Line 8: @@
 ===== 5.2 Recurrence Relations =====
+There are various other recurrence relations that correspond to different Divide and Conquer algorithms. For instance, Mergesort divides its input into q=2 subproblems of n/2 size, but other algorithms can have q>2 subproblems. Such a recurrence relationship would look like qT(n/2) + cn (or O(n)). //Question: What is the difference between writing O(n) or cn in the recurrence relationship?// A relationship with only q=1 subproblems would simply be T(n/2) + cn, which translates to O(n) run time. However, not all recurrences can combine two subproblems in O(n) time. In some instances it can simply be O(1), and in others, like in decaying geometric sums, it can be O(n^2). Thus, there are many different possible recurrence relationships for Divide and Conquer algorithms. The readability of this section is 4/10 because it involved a lot of complex math.
 ===== 5.3 Counting Inversions =====
+The motivation of the problem is preference rankings. Suppose we wish to create an algorithm that compares the rankings of one individual to another's. Similar rankings have very little differences, and different rankings have, obviously, a great deal of differences. In this sense, when comparing two rankings we wish to count the number of inversions as an indication of how similar/different the two rankings are. An algorithm that performs this type of comparison can run in O(nlogn) time. This algorithm makes use of a routine called Merge-and-Count, which takes two sorted lists A and B and both simultaneously adds elements from A and B into a combined sorted list C and counts the number of inversions. This itself takes O(n) time but is only one part of the overall algorithm.
+  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
+Overall, the readability of this section is 7/10.