**Next:**Computer Design

**Up:**Michaelmas Term 2007: Part

**Previous:**Michaelmas Term 2007: Part

**Contents**

##

Algorithms II

*Lecturer: Dr F.M. Stajano*

*No. of lectures:* 8

*Prerequisite courses: Algorithms I (CST students) or Data Structures and Algorithms (Diploma)*

*This course is a prerequisite for Computer Graphics and Image Processing, Complexity Theory, Artificial Intelligence I.*

**Aims**

The aim of this course is to give further insights into the design and analysis of non-trivial algorithms through the discussion of several complex algorithms in the fields of graphs and computer graphics, which are increasingly critical for a wide range of applications.

**Lectures**

**Advanced data structures.**Fibonacci heaps. Disjoint sets. [Ref: Ch 20, 21] [1-2 lectures]**Graph algorithms.**Graph representations. Breadth-first and depth-first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Shortest paths. Bellman-Ford and Dijkstra algorithms. Maximum flow. Ford-Fulkerson method. Matchings in bipartite graphs. [Ref: Ch 22, 23, 24, 25, 26] [4-5 lectures]**Geometric algorithms.**Intersection of segments. Convex hull: Graham's scan, Jarvis's march. [Ref: Ch 33] [1-2 lectures]

**Objectives**

At the end of the course students should

- have a good understanding of how several elaborate algorithms work
- have a good understanding of how a smart choice of data structures may be used to increase the efficiency of particular algorithms
- be able to analyse the space and time efficiency of complex 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 2*. (note that C and C++ editions are also available and are equally good for this course). Addison-Wesley. ISBN 0-201-36121-3.

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

Students are expected to buy and make extensive use of one of the
above references: those not doing so will be severely disadvantaged.
The easiest and recommended choice is Cormen *et al.* which
covers all the topics in the syllabus: 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:**Computer Design

**Up:**Michaelmas Term 2007: Part

**Previous:**Michaelmas Term 2007: Part

**Contents**