Course material 2010–11

##

Paper 1: Algorithms I

*Lecturer: Dr F.M. Stajano*

*No. of lectures:* 12

*Prerequisite course: Discrete Mathematics I*

*This course is a prerequisite for Algorithms II, Artificial Intelligence and Prolog.*

**Aims**

The aim of this course is to provide an introduction to computer algorithms and data structures, with an emphasis on foundational material.

**Lectures**

**Sorting.**Review of insertion sort, merge sort and quicksort. Understanding their memory usage with arrays. Heapsort. Other sorting methods. Finding the minimum and maximum. [Ref: Ch 1, 2, 3, 4, 15, 16] [4 lectures]**Algorithm design.**Ideas for algorithm design: dynamic programming, divide and conquer, greedy algorithms and other useful paradigms. [Ref: Ch 2, 15] [2 lectures]**Data structures.**Abstract data types. Pointers, stacks, queues, lists, trees. Hash tables. Binary search trees. Red-black trees. B-trees. Priority queues and heaps. [Ref: Ch 10, 11, 12, 13, 18, 19, 20, 21] [6 lectures]

**Objectives**

At the end of the course students should

- have a good understanding of how several fundamental algorithms work, particularly those concerned with sorting and searching;
- have a good understanding of the fundamental data structures used in computer science;
- be able to analyse the space and time efficiency 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. (2009). *Introduction to Algorithms*. MIT Press (3rd ed.). ISBN 0-262-53196-8

Sedgewick, R. (2004). *Algorithms in Java* vol. 1 (note that C and C++ editions are also available and are equally good for this course). Addison-Wesley. ISBN 0-201-36120-5. New edition forthcoming in 2008.

Kleinberg, J. & Tardos, É. (2006). *Algorithm design*. Addison-Wesley. ISBN 0-321-29535-8.

Knuth, D.E. (1997). *The art of computer programming* (three volumes so far; a boxed set is also available). Addison-Wesley (3rd ed.). ISBN 0-201-89683-4, 0-201-89684-2 and 0-201-89685-0.

Students are expected to buy, make extensive use of, and keep as
reference for their future career, one of the above textbooks: those not
doing so will be severely disadvantaged. The recommended choice is
Cormen *et al.* which, in spite of its superb quality, is the cheapest
(about 35 GBP new for over 1300 pages). The pointers in the syllabus are
to chapters in the second edition of that book. The other textbooks are
all excellent alternatives and their relative merits are discussed in
the course handout.