Course Outline

The course presents “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 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 dynamic programming, linear programming, computational geometry, and perhaps approximation algorithms.

  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.