Course pages 2012–13

# Algorithms II

**Principal lecturer:** Dr Frank Stajano**Taken by:** Part IB**Past exam questions****Information for supervisors** (contact lecturer for access permission)

No. of lectures: 12

Suggested hours of supervisions: 3

Prerequisite courses: Algorithms I

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

## 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. Van Emde Boas trees. [Ref: Cormen et al. Ch 19, 20, 21] [4 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] [6 lectures]**Multithreaded algorithms.**Matrix multiplication. Mergesort. [Ref: Ch 27] [1 lecture]**Geometric algorithms.**Intersection of segments. Convex hull: Graham’s scan, Jarvis’s march. [Ref: Ch 33] [1 lecture]

## 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. (2009). *Introduction to Algorithms*. MIT Press (3rd 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. New edition forthcoming in 2008.

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

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.