Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter5 [2018/03/12 21:38] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter5 [2018/03/12 21:51] (current) – devlinn
@@ Line 10: / Line 10: @@
 These types of algorithms need a base case. We then need to denote //T//(//n//) as the worst-case running time for a given problem of this type. We then break this running time down as the algorithm divides and conquers and we end up with a //recurrence relation//. There are two basic ways to solve a recurrence: 1.) "unroll" the recursion; and 2.) guess and check.
-Looking at Mergesort as an example, we can see how the process of unrolling takes place: we must identify a pattern in the running time across the first few levels, sum the running times over all levels, and arrive at a total running time. We can see that the first level of Mergesort has a problem of size //n// and takes at most //cn// time plus all the time spent in remaining recursive calls, the next level has two problems of size //n///2, taking at most //cn///2, two times, so //cn/, etc. To identify a pattern, we see than at level //j//, there are now //cn///2<sup>//j//</sup> problems 2<sup>//j//</sup> times, which is simply //cn//. We then sum over all levels of recursion and see it takes log<sub>2</sub>//n// times to half the input to bring it from size //n// to size 2 (our base case). Since we are doing //cn// work at every level, the total running time is //O//(//n//log//n//).
+Looking at Mergesort as an example, we can see how the process of unrolling takes place: we must identify a pattern in the running time across the first few levels, sum the running times over all levels, and arrive at a total running time. We can see that the first level of Mergesort has a problem of size //n// and takes at most //cn// time plus all the time spent in remaining recursive calls, the next level has two problems of size //n///2, taking at most //cn///2, two times, so //cn//, etc. To identify a pattern, we see than at level //j//, there are now //cn///2<sup>//j//</sup> problems 2<sup>//j//</sup> times, which is simply //cn//. We then sum over all levels of recursion and see it takes log<sub>2</sub>//n// times to half the input to bring it from size //n// to size 2 (our base case). Since we are doing //cn// work at every level, the total running time is //O//(//n//log//n//).
 This section is a little bit challenging to understand for me. I have a hard time with the concept of calculating the recurrence relation. I guess more practice might help. I would rate my understanding at a solid 6 right now.
@@ Line 25: / Line 25: @@
 This algorithm has the following recurrence: //T//(//n//) ≤ 2//T//(//n///2) + //cn//<sup>2</sup>. The running time in this case is //O//(//n//<sup>2</sup>).
+===== 5.3 Counting Inversions =====
+We can apply the divide-and-conquer method to many problems, including counting the number of inversions, which compares rankings and looks at those which are "out of order". Given a list of numbers A, we say that two indices //i// and //j//, where //i// < //j//, form an inversion if //a<sub>i</sub>// and //a<sub>j</sub>// are out of order (//a<sub>i</sub>// > //a<sub>j</sub>//). The Merge-and-Count Algorithm can be used to find the number of inversions given a list which has been divided in half and sorted.Here is the algorithm:
+    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 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
+Merge-and-Count takes //O//(//n//) time. I understand this section very well since we went over it in class very thoroughly. It helps to run through an interactive example. I would rate my understanding an 8.