**Next:**Paper 2: Probability

**Up:**Easter Term 2009: Part

**Previous:**Easter Term 2009: Part

**Contents**

##

Paper 1: Algorithms I

*Lecturer: Dr F.M. Stajano*

*No. of lectures + practicals:* 12 + 3

*Prerequisite course: Discrete Mathematics I*

*This course is a prerequisite for Algorithms II 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**

**Algorithm fundamentals.**Algorithm analysis and design. Models of a computer; costs. Asymptotic notation. Computational complexity. Recurrences. Ideas for algorithm design: divide and conquer, dynamic programming, greedy algorithms and other useful paradigms. [Ref: Ch 1, 2, 3, 4, 15, 16] [2-3 lectures]**Sorting.**Insertion sort. Merge sort. Heapsort. Quicksort. Other sorting methods. Finding the minimum and maximum. [Ref: Ch 2, 6, 7, 8, 9] [4-5 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] [5-7 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. (2001). *Introduction to Algorithms*. MIT Press (2nd 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 and make extensive use of one of the
above textbooks: those not doing so will be severely disadvantaged.
The recommended choice is Cormen *et al.* which covers all
the topics in the syllabus of Algorithms I and II and, in spite of its
quality, is the cheapest. The pointers in the syllabus are to chapters
in that book. The other textbooks are all excellent alternatives and
are sometimes clearer or more detailed than Cormen, but they are not
guaranteed to cover every item in the syllabus. Their relative merits
are discussed in the course handout.

**Next:**Paper 2: Probability

**Up:**Easter Term 2009: Part

**Previous:**Easter Term 2009: Part

**Contents**