Hacker News Reader

That's interesting. I hadn't run into this before in college or grad school, and it seems like a good way of bridging the analytical gap between theory and practice that Sedgewick talked about.

It's unlikely that Sedgewick hadn't heard of this before. I suspect that he didn't mention it simply because it isn't often taught. According to your citation, it was introduced in 2001 which is quite recent in academic terms. How did you come across it?

View on HN

Yes, it is quite interesting, and although the main idea is straightforward, the analysis of concrete algorithms gets quite technical. Also, it's still actively researched and maybe not entirely accepted into the mainstream yet. AFAIK it has been successfully applied to many well-known algorithms which have bad worst-case, but surprisingly good behavior in practice (e.g. quicksort). I heard about it from my advisor.

Spielman and Teng are very famous, and have received even a Godel prize for their work in smoothed analysis. Currently they're doing some very interesting things with efficient algorithms on graphs laplacians and linear systems, you can see Spielman's talk at last FOCS, it's very enlightening: http://weyond.com/www/focs/2010/downloads/1335.f4v

Reply on news.ycombinator.com