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.).
