Design and Analysis of Algorithms Neal Young

Computer Science 45

Presentation Topics I'd like each of you to teach a 1/2 hour session on some relevant topic during the last two days of class.

Here are some suggested topics; you are free to choose one not on this list.

1. Least squares approximation (linear algebra) - CLR 31.4
2. Fast fourier transforms and multiplying polynomials - CLR 32
3. Boyer-Moore string matching - CLR 34.5
4. Connected components on a PRAM (parallel algorithms) - CLR problem 30-3
5. Skip lists - paper by Bill Pugh
6. A topic in computational geometry (e.g. finding the convex hull or nearest neighbors of a set of points in the plane) - CLR 35
7. A topic in approximation algorithms (e.g. vertex cover, traveling salesman, set-cover, subset-sum) - CLR 37