Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/12 00:11] – [Chapter 5.3: Counting Inversions] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/12 01:47] (current) – [Chapter 5.5: Integer Multiplication] nollets
@@ Line 29: / Line 29: @@
 ===== 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.