Computer Laboratory – Course material 2007

Next: Computer Perspectives Up: Easter Term 2008: Part Previous: Easter Term 2008: Part Contents

Algorithms I

This course is taken by all Part IA students.

Lecturer: Dr K.A. Fraser

No. of lectures: 12

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]
Simple data structures. Array, linked list, dynamic allocation, compound structures. [1 lecture]
Sorting. Selection, Insertion, Shell, Quick, Heap, Merge. Sorting faster than O(n log n): Counting, Bucket, Radix. [5 lectures]
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.).

Next: Computer Perspectives Up: Easter Term 2008: Part Previous: Easter Term 2008: Part Contents