Differences

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

--- courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 18:30] – created boyese
+++ courses:cs211:winter2018:journals:boyese:chapter5 [2018/03/12 19:29] (current) – [Section 5.3: Counting Inversions] boyese
@@ Line 1: / Line 1: @@
 ====Section 5.1: A First Recurrence: The Mergesort Algorithm====
+**Divide and Conquer Algorithms**
+  * Process
+      * Break up problem into several parts
+      * Solve each part recursively
+      * Combine solutions to sub-problems into overall solution
+      * Use recurrences to analyze the runtime of divide and conquer algorithms
+  * Approaches to Solving Recurrences
+      * Unroll recursion
+          * Look for patterns in runtime at each level
+          * Sum up running times over all levels
+      * Substitute guess solution into recurrence
+          * Check to make sure it works
+          * Prove that it works using induction on n
+**Merge Sort**
+  * Analyzing Merge Sort
+      * General Template:
+          * Break up problem of size n into two equal parts of size 1/2n → O(1)
+          * Solve two parts recursively → T(n/2) + T(n/2)
+          * Combine two solutions into overall solution → O(n)
+      * Definition: T(n) = the number of comparisons to merge sort an input of size n
+          * Recurrence relation: T(n) = 2T(n/2) + O(n)
+              * T(n) =T(n/2) + c
+          * Cost of each level in the tree is c*n
+              * log n levels
+          * Run time = log n
 ====Section 5.2: Further Recurrence Relations====
+**Binary Search**
+  * Analyzing the algorithm
+      * Instead of recursively solving 2 problems, solve q problems
+          * Size of problems is still n/2
+      * Combining solutions is still O(n)
+      * Recurrence relation:
+          * For some constant c, T(n) ≤ qT(n/2) + cn when n > 2 and T(2) < c
+  * Unroll the recurrence
+      * T(n) = T(n/2) + c
+          * Constant work at each level
+          * Number of levels = log n
+          * So the runtime is O(log n)
+      * The case of q > 2
+          * First level: qT(n/2) + cn
+          * Next level: qT(n/4) + c(n/2)
+          * qk problems at level k
+          * size: n/2<sup>k</sup>
+          * Number of levels: log n
+              * Each level takes q<sup>k</sup> * c * (n/2<sup>k</sup>) = (q/2)icn
+          * Overall run time: O(n<sup>log q</sup>)
 ====Section 5.3: Counting Inversions====
+**Comparing rankings**
+  * To determine similarity of rankings we need a metric
+  * Similarity metric: number of inversions between two rankings
+      * My rank: 1, 2, …, n
+      * Your rank: a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>
+      * Indices i and j are inverted if i < j but a<sub>i</sub> > a<sub>j</sub>
+      * Geometric series
+**Brute force solution**
+  * Look at every pair (i, j) and determine if they are an inversion
+  * Requires Θ(n<sub>2</sub>) time
+      * Note: already an efficient algorithm but we can try to improve on run time
+**Divide and conquer**
+  * Assume number represents where item should be in the list, i.e., where it is in someone else’s list
+  * Divide: separate list into two pieces
+  * Conquer: recursively count inversions in each half
+  * Combine: count inversions where ai and aj are in different halves, and return sum of three quantities
+//Merging two sorted lists while also counting the number of inversions between them.//
+<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 a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the Cuwent pointer
+        Append the smaller of these two to the output list
+        If b<sub>j</sub> 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
+</code>
+//The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.//
+<code>
+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](ceiling) elements
+            B contains the remaining [n/2](floor) elements
+        (r<sub>A</sub>, A) = Sort-and-Count (A)
+        (r<sub>B</sub>, B) = Sort-and-Count (B)
+        (r, L) = Merge-and-Count (A, B)
+    Endif
+    Return r = r<sub>A</sub> + r<sub>B</sub> + r, and the sorted list L
+</code>