Differences

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

--- courses:cs211:winter2018:journals:goldm:ch5 [2018/03/12 20:09] – goldm
+++ courses:cs211:winter2018:journals:goldm:ch5 [2018/03/12 20:23] (current) – [5.3: Counting Inversions] goldm
@@ Line 18: / Line 18: @@
 ===== 5.3: Counting Inversions =====
+The beginning of this section discusses rankings. It gives collaborative filtering and meta-search tools as examples of applications that rely on rankings. In comparing sets of rankings, one can do so by counting the number of inversions. We then seek to find an algorithm that will count inversions. We ultimately will be able to count inversions in O(nlogn). We start by splitting the set in two. We then count the number of inversions in each half. Then we count the number of inversions that belong to the other half. We recursively sort the numbers in each set to aid us in our inversion search.
+From this, we have the following pseudo code.
+Merge-and-Count(A,B)
+-Maintain a Current pointer into each list, initialized to point to the front elements
+-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 then
+---Increment Count by the number of elements remaining in A
+--Endif
+--Advance the Current pointer in the list from which the smaller element was selected.
+-EndWhile
+-Once one list is empty, append the remainder of the other list
+to the output
+-Return Count and the merged list
+We call this as a recursive subroutine to ultimately get the final number. This is done in the following pseudocode.
+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)
+-Endif
+-Return r=rA+rB+r, and the sorted list L
+Ultimately, we are able to implement this in O(nlogn) as desired.
+I felt this section was weaker than the previous one. I know it had to, but it only focused on one problem. I also found this section particularly boring, possibly because I have already read the other three. Regardless, I give it a 4.5/10.