Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2011:journals:andrew:chapter5 [2011/03/09 14:08] – created bennetta | courses:cs211:winter2011:journals:andrew:chapter5 [2011/03/14 20:31] (current) – bennetta | ||
|---|---|---|---|
| Line 33: | Line 33: | ||
| ===== Final Thoughts ===== | ===== Final Thoughts ===== | ||
| This chapter is probably my weakest chapter so far and, as a result, I am not as able to adequately put this chapter into my own words based on my knowledge from class discussions and my reading of the chapter. That being said, I should take this as a sign that I need to see Prof. Sprenkle this afternoon for help on this difficult subject. Readability: | This chapter is probably my weakest chapter so far and, as a result, I am not as able to adequately put this chapter into my own words based on my knowledge from class discussions and my reading of the chapter. That being said, I should take this as a sign that I need to see Prof. Sprenkle this afternoon for help on this difficult subject. Readability: | ||
| + | |||
| + | ===== 5.5: Integer Multiplication ===== | ||
| + | * Using divide and conquer to multiply integers: | ||
| + | * This chapter seeks to improve on the basic integer multiplication algorithm (currently n^2) | ||
| + | * Divide into n/2 bits using 3 recursive calls. | ||
| + | * O(n^1.59) | ||
| + | |||
| + | ===== 5.6: Convolutions and the Fast Fourier Transform ===== | ||
| + | * Basic recurrence in the design of the Fast Fourier Transform: | ||
| + | * Deals with combining vectors. Used in signal processing. | ||
| + | * Design and analysis of this algorithm using recurrence can be found on pages 238 - 242 | ||
| + | |||
| + | |||
| + | |||
