Differences

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

--- courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:20] – [5.5 Integer Multiplication] 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 -- O(n) time -- 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 is all explained well on the bottom of page 232
+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).