Course pages 2011–12

# Algorithms I

**Principal lecturer:** Dr Frank Stajano**Taken by:** Part IA CST, Part IA NST, Part I PPS**Past exam questions:** Algorithms I, Algorithms**Information for supervisors** (contact lecturer for access permission)

No. of lectures: 15 (Continued into Easter Term)

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 complexity, O-notation, insertion sort, merge sort and quicksort. Understanding the memory behaviour of these algorithms with statically allocated arrays. Heapsort. Other sorting methods including sorting in linear time. Median and order statistics. [Ref: Cormen et al. Ch 1, 2, 3, 4, 6, 7, 8, 9] [about 4.5 lectures]**Strategies for algorithm design.**Dynamic programming, divide and conquer, greedy algorithms and other useful paradigms. [Ref: Ch 4, 15, 16] [about 3.5 lectures]**String matching.**Naive strategy. Rabin-Karp. Finite automata. [Ref: Ch 32] [about 1 lecture]**Data structures.**Abstract data types. Pointers, stacks, queues, lists, trees. Binary search trees. Red-black trees. B-trees. Hash tables. Priority queues and heaps. [Ref: Ch 6, 10, 11, 12, 13, 18] [about 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 978-0262533058

Sedgewick, R. & Wayne, K. (2011). *Algorithms*. Addison-Wesley (4th ed.). ISBN 978-0321573513.

Kleinberg, J. & Tardos, É. (2006). *Algorithm design*. Addison-Wesley. ISBN 9780321372918.

Knuth, D.E. (2011). *The art of computer programming*. Addison-Wesley (3rd ed.). ISBN 978-0321751041.

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, covers the whole syllabus and is one of the cheapest (about 35 GBP new for over 1300 pages). The other textbooks may not cover the whole syllabus but are all excellent resources; their relative merits are discussed in the course handout.