**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**