Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/11 23:34] – [Chapter 5.2: Further Recurrence Relations] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/12 01:47] (current) – [Chapter 5.5: Integer Multiplication] nollets
@@ Line 23: / Line 23: @@
 ===== Chapter 5.3: Counting Inversions=====
+This section discusses the problem that occurs when trying to see how similar two people's preferences were. Many websites use this idea in order to best suggest things related to a person's preferences. The most natural way to do this is by counting inversions, or counting the number of switches we have to make to one list in order to make it match the first list. In order to determine this number of inversions in  more efficient time (something better than O(n^2)) we have to split the list in half, and then count the number of inversions in each half. Then we sort each half and use Merge-and-Count (on page 224 of the text). This will bring the two list back together and count the number of inversions. The Merge-and-Count runs in O(n) time, and the sorting of each list is O(logn) meaning the inversion counting takes O(nlogn) time.
+We went over this algorithm pretty well in class and the section helped back it up. It was relatively helpful and clear. I would give it a 7/10. I felt that it was better explained and written out in the slide.
 ===== Chapter 5.4: Finding the Closest Pair of Points=====
+This algorithm BLEW MY MIND.
+This section discussed the closet pair problem, where we want to find the closet pair of points in a plane. We first assume that no two points have the same x and y coordinate. The general idea of solving this problem is to divide the points into left and right sections, find the closest pair of points in each of these sections, and then determine if there are any pairs of points along the border of the two halves. In order to find the closest pairs of points in each half, we first sort the halves by their x and y coordinates (so that they are on a line) and look at the points closest to each other. Once we find the closest pair in each side, we can then create a distance delta. We then take that distance delta and look within the delta of the "border" or midpoint for two points closer together. In order to find the closest pair in this middle section of the plane we use the Closet-Pair-Rec algorithm (on page 230 in the text) which runs in O(n) time (this is the MIND BLOWING part). Then, using this ability to find the closest pair in the mid-section in O(n) time, we can  find the closest pair in the whole plane in O(nlogn) time.
+This discussion in class was very helpful and the book was a good reinforcement of the discussion.
+I would give this section an 8/10 because this is a pretty interesting algorithm and a cool way to find the shortest path.
 ===== Chapter 5.5: Integer Multiplication=====
+In this section we look at a way to make the multiplication of two integers run in less than O(n^2) time. In order to do this, rather than using the traditional method, in which you multiply each digit in one integer by the other digits in the other integer and then adding the results together.
+The change the algorithm, the section first looked at splitting the multiplication process into 4 parts of n/2 size. However, this runs in O(n^2) time, which is not an improvement.
+If we instead divide the multiplication into 3 parts of n/2 size, we can have the algorithm run in (n^1.59) time. The algorithm (one page 233 in the text)finds a way to split the multiplication process into these three parts. We then write x1y1*2^n+(p-x1y1-x0y0)*2^n/2+x0y0 and we are able to achieve our wanted run time.
+This section was short and sweet, which was nice. I did not know that was how you multiplied binary numbers (we learned a different way in 210). I would give it a 8/10.