I've been meaning to get around to reading those notes. A friend of mine also told me about this course: http://www.cs.sunysb.edu/~skiena/392/ - taught by Steven Skiena (author of The Algorithm Design Manual).
I wish my university had more courses like this, but for now I'll have to learn from these.
I never really learned anything about pure algorithms in high school, but it seems like quite a bit of people in my program covered the basics at their school. I want to learn more about this style of programming so that I can compete on sites like TopCoder, but I never know where to start. I'm guessing these notes are good, but now I just need to find the time to study the material.
The notes for the algorithms class here at Berkeley were extracted into a pretty good textbook. You can get a draft of it here: http://www.cs.berkeley.edu/~vazirani/algorithms.html. It's worth a look if you're interested in basic algorithm concepts. (The book is for the undergraduate introduction to algorithms class and offers a good overview of the subject, but nothing super advanced.)
While it was published as a book, it really is just a neater version of the lecture notes for the class.
Why do algorithm books generally devote so much space to FFT?
It seems like it has very narrow applicability: apart from signal processing and multiplying big integers or polynomials, what else are they useful for?
Wouldn't it be better to explain divide-and-conquer with some other algorithm having broader applicability?
I've always had the feeling that FFT is taught in the wrong way, at least in CS courses. They just introduce complex roots of unity and this magic Vandermonde matrix and then they state a scary "convolution theorem", and after a lot of handwaving you see that you can use it for polynomial multiplication. This gives basically no insight about why things work.
With just a little bit of linear algebra and abstraction it is easy to gain a lot of insight about Fourier transform. For example this is the way I see it:
* First you introduce shift-invariant linear operators (circulant in the finite-dimensional case), i.e. linear operators that don't change if you shift the vector, apply the operator and then shift it back.
* Then you show that the Fourier basis is THE basis that diagonalizes shift-invariant operators. This is just matter of multiplying the Fourier vectors with the shift operator and noticing that you get back the same vectors, and it is where the cyclicity of the roots of unity comes into play. This also explains why Fourier transform works for signal processing: if you have to operate in the frequency domain, shifting your signal in time shouldn't change anything.
* Then you show that convolution (or polynomial multiplication) is shift-invariant: this is just matter of writing down a convolution and doing a change of variable
* You are done: if convolution is diagonal in the Fourier basis, it can be applied just by multiplying its coefficients in the Fourier domain.
* Now you introduce FFT as an efficient way of computing Fourier transform, but only after you understood what the transform is doing.
When I realized this, something "clicked" in my mind and I finally "understood" Fourier analysis.
Maybe I should expand on this a bit more and write a blog post about it without all the complications that I find in books.
I wouldn't call signal processing "narrow applicability." Signal processing is important for a wide range of computer science applications, for example any voice processing with regard to AI or security (think Siri!), and many programmers will at some point call FFT without really knowing what it is (happened to me twice this year already). Having read the FFT bits really helped to understand what it does. It also happens to be a really cool application of divide and conquer that was absolutely groundbreaking. So like from a practical, historical, and cleverness standpoints, it seems like a great thing to describe. I'm not sure it's important at all to remember how it works, but having some kind of idea of how it works seems valuable.
And it probably just takes a lot of space because it's complicated. Haha.
I think the FFT is just a good case study for how to design nontrivial algorithms. The point isn't so much to teach you super useful algorithms as to show you how you can come up with them yourself, and what sort of thinking that would take. For what it's worth, the book does cover a bunch of other divide and conquer algorithms as well.
The Berkeley book is quite good. Pretty concise description of the fundamental stuff and good exercises. I'm actually a student at UIUC and Jeff's notes (the ones in the link) are great too and he often includes areas of theory not found in the Berkeley book that he finds interesting.
Just took an exam in UIUC's CS473 yesterday (http://www.cs.uiuc.edu/class/sp12/cs473) -- the two cited references are Jeff Erikson's notes as well as the Berkeley textbook (we refer to it as "the Dasgupta book"). I personally found the Dasgupta book an easier read / good introduction before reading Erikson's notes. Both were invaluable studies and in retrospect all interview questions basically test this information, for those either not in university or wanting to learn to ace those big-O rundowns.
If I wasn't in / wasn't able to attend / dropped out of college, I'd just sit and read all of these notes and I'd probably be okay.
I wish my university had more courses like this, but for now I'll have to learn from these.
I never really learned anything about pure algorithms in high school, but it seems like quite a bit of people in my program covered the basics at their school. I want to learn more about this style of programming so that I can compete on sites like TopCoder, but I never know where to start. I'm guessing these notes are good, but now I just need to find the time to study the material.