Differences

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

--- courses:cs211:winter2011:journals:charles:chapter5 [2011/03/11 21:07] – [5.3 Counting Inversions] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:57] (current) – [5.6 Convolutions and the Fast Fourier Transform] gouldc
@@ Line 22: / Line 22: @@
 I don't get the final problem section 'Identifying a pattern' on page 221. It says "and hence the total work at this level is bounded by ... cn^2/2^j." But in the section 'Analyzing the first few levels' it says that the third level (j=3) runs for a total of at most cn^2/4. Shouldn't it be cn^2/8?
 ===== 5.3 Counting Inversions =====
-This section is about comparing ranking systems. Websites like Amazon and YouTube do to direct their customers/viewers to other products/videos they may like. It generalizes the problem drastically, as we start by thinking about the similarities/differences between two sets of integers.
+This section is about comparing ranking systems. Websites like Amazon and YouTube do this to direct their customers/viewers to other products/videos they may like. We generalize the problem drastically, as we start by thinking about the similarities/differences between two sets of integers.
-Example: Person A has a preference list for n pizza joints, which we write as follows. 1, 2, 3, .., n (the 1st pizza place is his most favorite, and the nth pizza place is his least favorite). Another person has a different preference list. The goal is to find "a measure that tells us how far this list is from being in ascending order."
+Example: Person A has a preference list for n pizza joints, which we write as follows: 1, 2, 3, .., n (the 1st pizza place is his most favorite, and the nth pizza place is his least favorite). Another person has a different preference list. (The 1st pizza place may be his second most favorite, for example.) The goal is to find "a measure that tells us how far this list is from being in ascending order."
+Inversions are the solution. An inversion is an instance in which two elements are "out of order." The Sort-and-Count algorithm on page 225 is an example of recursive procedure that "simultaneously sorts and counts the number of inversions in a list L."
+(5.7) 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.
 ===== 5.4 Finding the Closest Pair of Points =====
-...
+We hammered this home in class. To solve the problem, one must first sort all of the points by their x-coordinates. Then one divides the problem into two subproblems of equal size (those with the smallest x-coordinates in one half, the rest in the other). Then the algorithm recursively finds the closest pair of points in each subarea. Having solved those problems, they need to be combined... since it is possible for the closest pair of points to be somewhere in between the subareas. This is all detailed in this section, and I understand it well because we hammered it down in class.
+(5.12) The running time of the [Closest-Pair] algorithm is O(n log n).
 ===== 5.5 Integer Multiplication =====
-...
+This problem gives an algorithm that multiplies integers in sub-quadratic time (better than we usually do when we multiply by hand). It computes the product xy by recursively dividing x and y in half and performing operations on those (n/2)-digit segments. It relies on fewer multiplications and more additions (pp. 232-233 explain this well).
+This example shows why thinking about recurrence relations can be useful. For example, we knew that dividing the problem into any more than 3 subproblems (with linear time combination &etc) would result in an equivalent or worse running time than the normal algorithm. Therefore we looked for a way to divide the problem into 3 subproblems (while maintaining linear time combination &etc). Sure, it required our being clever, but the understanding of recurrence relations made it easier than it would have been.
 ===== 5.6 Convolutions and the Fast Fourier Transform =====
-...
+I learned a new math term: convolution. Convolutions are a yuge deal in signal processing. This section gives a sub-quadratic algorithm for computing the convolution. The Fast Fourier Transform computes the convolution in O(n log n) time. (5.15).