Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter5 [2018/03/12 16:45] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter5 [2018/03/12 17:06] (current) – thetfordt
@@ Line 18: / Line 18: @@
 I would rate the readability of this section at 8/10. Some parts were difficult to follow(partial substitution). However, others flowed very smoothly.
+===== Section 5.3 - Counting Inversions =====
+The section begins by discussing a problem. In this section, the book seeks to address the problem surrounding rankings. If we have two sets of rankings, and we want to investigate how closely related this set of rankings is to another set, this could tell us whether or not people have similar rankings. And a way to quantify this subjective relation is by means of counting inversions.
+The brute force way of doing this is, given two sets of numbers with corresponding positions, we could examine every pair of numbers and see if they are inverted, which would yield a runtime of O(n^2). We seek to shrink this down to O(nlogn).
+In order to do this, we create and use two separate algorithms. The first of these is the Merge-and-Count algorithm. In this algorithm, we are given as input two sorted lists. We initialize a pointer to the front of each of these lists and maintain a variable count (to count inversions) starting at 0. While both of our input lists of nonempty, we let a_i and b_j be the elements pointed to by the Current pointer, append the smaller of these two to the output list, if b_j is the smaller element then we increment count by the number of elements remaining in A, then after that, we advance the Current pointer in the list from which the smaller element was selected. (endwhile) And once one of the two lists is empty, append the remainder of the other list to the output (the new sorted list). Note that the runtime of the Merge-and-Count algorithm is O(n).
+Now, we can use this algorithm to create a new algorithm to count inversions in a given unsorted list. The text calls this algorithm Sort-and-Count. This algorithm takes a list as input. If the list has one element then there are no inversions. Otherwise, it divides the list into two halves, A containing the first [n/2] elements and B containing the remaining [n/2] elements. We then let (r_A,A) = Sort-and-Count(A), (r_B,B) = Sort-and-Count(B), and (r,L) = Merge-and-Count(A,B). Note the original input list is called L. And since Merge-and-Count runs in O(n) time, and we will divide the list log(n) to count inversions, our Sort-and-Count algorithm will run in O(n log n) time.
+I would rate the readability of this section at 8/10.