Differences

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

--- courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:17] – gouldc
+++ courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:57] (current) – [5.6 Convolutions and the Fast Fourier Transform] gouldc
@@ Line 34: / Line 34: @@
 (5.12) The running time of the [Closest-Pair] algorithm is O(n log n).
 ===== 5.5 Integer Multiplication =====
-Multiplying n-digit integers requires n^2 partial products, right? No, if we divide each n-digit integer (x and y, say) into an (n/2)-digit integer, we can reduce the cost of computing xy by relying more on fewer multiplications, more additions, and basically our cleverness.
+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).
-Assuming we know that "normal" multiplication takes O(n^2) time, then how could we formulate a feasible recurrence relation that gives a better solution?
+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).