This is the first PhD-level course on the design and the analysis of
efficient algorithms, with a strong emphasis on theoretical aspects. The
prerequisites are a very basic knowledge of graph theory and
computational complexity, as well as a good understanding of
undergraduate-level courses of algorithms, discrete mathematics, and
It is not necessary to have already taken a graduate-level course on algorithms.
The goal of the course is to give a broad coverage of the main techniques in algorithm design and analysis, so that the course can be useful also for a researcher in a different field. To this purpose, the computational problems tackled are among the most basic problems on strings and graphs, such as pattern matching, vertex cover and max cut.
In fact, anyone that deals with one of the following questions will find the course interesting.
- How can I cope with problems that are provably hard to solve exactly (i.e. are NP-hard)?
- How can I exploit the massive availability of CPUs?
- How can I query efficiently massive texts?