Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:39] – [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 38: | Line 38: | ||
| 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. | 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 ===== | ===== 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). |
