This course is a prerequisite for Algorithms II and Prolog.

Aims

The aim of this course is to provide a general introduction to
a range of algorithms for solving classical (and practical) problems
in computer science, and methods for analysing and comparing them.

Lectures

Fundamentals.
Models of a computer, costs, growth rates.
Abstract data types: interface versus implementation. [1 lecture]

Searching.
The set abstract data type.
Binary search tree, hash table, radix tree.
Guaranteed bounds: 2-3-4, red-black, splay tree.
Probabilistic bounds: skip list.[5 lectures]

Objectives

At the end of the course students should

have a good understanding of how a range of fundamental
algorithms work, particularly those concerned with the classical
problems of sorting and searching

be able to analyse the efficiency in terms of space and
time of most algorithms

be able to design new algorithms or modify existing ones for new
applications and reason about the efficiency of the result

Recommended reading

* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2001). Introduction to Algorithms. MIT Press (2nd ed.). ISBN 0-262-53196-8
Sedgewick, R. (2003). Algorithms in Java. Addison-Wesley (3rd ed.).