Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter5 [2018/03/10 19:50] – [5.2 Further Recurrence Relations] patelk
+++ courses:cs211:winter2018:journals:patelk:chapter5 [2018/03/10 20:28] (current) – [5.3 Counting Inversions] patelk
@@ Line 106: / Line 106: @@
 ===== 5.3 Counting Inversions =====
+**The Problem**
+  * Rankings: becoming important to a number of current applications
+  * Collaborative Filtering: match your preferences with those of other people out on the Internest
+    * can then recommend new things that those other people have liked
+  * Meta-Search Tools: execute the same query on many different search engines and then try to synthesize the results by looking for similarities and differences among the various rankings that the search engine return
+  * Comparing Two Rankings:
+    * Natural Method: label the movies from 1 to n, order these labels according to the stranger's ranking, see how many out of order pairs there are
+      * Sequence of n numbers a1...an. Assume numbers are distinct; define a measure that tells us how far this list is from being in ascending order
+      * Count the number of inversions: if ever pair forms an inversion, there are (n choose 2) inversions.
+**Designing and Analyzing the Algorithm**
+  * Look at every pair of numbers (ai,aj) and determine whether they constitue an inversion -> O(n^2)
+  * Desired Time: O(nlogn)
+  * Set m = [n/2] and divide the list into two pieces a1,...,am and am+1,...,an.
+  * Count the number of inversions in each of these two halves separately
+  * Then count the number of inversions where the two numbers belong to different halves -> must do this in O(n) time
+    * the pairs (ai,aj) where ai is in the first half, aj is in the second half and ai>aj
+    * Recursively sort the numbers in the two halves
+    * Merge-and-Count: left with two sorted lists A and B
+      * produce a single sorted list C from their union, while counting the number of pairs(a,b) with an inversion.
+      * Walk through the sorted lists A and B, removing elements from the front and appending them to the sorted list C. In a given step, we have a Current pointer into each list, showing our current position.
+      * Every time ai is appended to C, no new inversions are encountered, since ai is smaller than everything left in list B, and it comes before all of them. If bj is appended, then there is an inversion so we increase our count of the number of inversions by the number of elements remaining in A. In constant time, we can account for all inversions.
+{{:courses:cs211:winter2018:journals:patelk:merge-and-sort3.png?nolink&400|}}
+{{:courses:cs211:winter2018:journals:patelk:merge-and-sort1.png?nolink&400|}}
+{{:courses:cs211:winter2018:journals:patelk:merge-and-sort2.png?nolink&400|}}
+  * The Sort-And-Count algorithm correctly sorts the input list and counts the number of inversions in O(nlogn) running time for a list with n elements
+==== Personal Thoughts ====
+I thought this section provided a very interesting algorithm to count the number of inversions in O(nlogn) time. The combination of this section and the classroom discussion did a pretty good job of helping me understand this material. It also helped that we were introduced to inversions in another chapter/section. This made it so that the concept as a whole wasn't as difficult to understand. The algorithm and runtime both make sense to me.
+Readability: 7.0
+Interesting: 7.0