Course Outline

The course presents “advanced” or “special” (hereinafter called “advanced”) algorithms, where the term “advanced” may have several meanings: for the purpose of the course an algorithm may be deemed advanced if it is particularly clever or useful (or represents a clever/useful line of algorithms), if it is used for an unexpected or interesting purpose, or if it is written for an advanced architecture (such as a massively parallel machine).

While a program runs on a computer, an algorithm “runs” on a computing model. Therefore, models of computation will also be addressed in the course.

The following topics are planned, though this is only a tentative schedule as time constraints or interest (mine as well as yours) may entail additions or modifications.

1. The theory of NP-completeness, which uses algorithms to translate rather than solve problems (2 weeks).

2. Algorithms that are advanced in the sense that the usual courses on the matter does not cover them (4 weeks). The tentative topics are approximation algorithms, linear programming, and computational geometry.

3. Parallel algorithms and models of computation, as well as the relation between them (5 weeks).

This is an advanced course that requires the active involvement of students. I will present in class the basic ideas and I will suggests some resources; however, it is your responsibility to find further documentation to complete your understanding of the matter at hand. Student presentation are to be expected and will be integral part of the lectures for the course.