Document Excerpts:

The study of algorithms - carefully-crafted solutions to particularly important programming problems - is one of the oldest areas in Computer Science. In order truly to understand an algorithm we have first to understand why it works at all, then to understand how it performs in general - how long it takes and how much space it takes tip while it is working - and last, understand how to tweak the algorithm to make its performance fit the particular circumstances in which we want to use it. In the case of some of the famous algorithms we shall meet, like quicksort, we also have to understand why it isn't easy to do better.

So the course will focus on two issues: correctness - how we say what an algorithm is supposed to do, and how we can argue that it actually does it -and so-called complexity - how to estimate the amount of work an algorithm must do to perform its task in general, or on average, or in the worst case. There will be some experimental work, trying to verify in practice the theoretical measures that can be developed by using mathematical arguments, but much of the course will be about analysing algorithms with pencil and paper.

Some of the algorithms we shall analyse are intensely beautiful. To appreciate their beauty we have to realise how much better they are than the first naive attempts one of us might make to solve the same problem, and how concisely they solve the problem which they are designed to solve. All of the algorithms we shall analyse are useful. Some of them are not entirely understood - it is a recurring feature of Computer Science that we continually invent things which we only partly understand.