Course pages 2013–14

# 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 and data structures of general applicability.

## Lectures

**Advanced data structures.**Amortized analysis. Fibonacci heaps. Van Emde Boas trees. Disjoint sets. [Ref: CLRS3 chapters 17, 19, 20, 21] [about 4-5 lectures]**Graph algorithms.**Graph representations. Breadth-first and depth-first search. Topological sort. Minimum spanning trees. Kruskal and Prim algorithms. Shortest paths. Bellman-Ford and Dijkstra algorithms. Maximum flow. Ford-Fulkerson method. Matchings in bipartite graphs. [Ref: CLRS3 chapters 22, 23, 24, 25, 26] [about 5-6 lectures]**Multithreaded algorithms.**Dynamic multithreading. Work and span. Scheduling. Race conditions. [Ref: CLRS3 chapter 27] [about 1 lecture]**Geometric algorithms.**Intersection of segments. Convex hull: Graham’s scan, Jarvis’s march. [Ref: CLRS3 chapter 33] [about 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
978-0-262-53305-8

Sedgewick, R., Wayne, K. (2011). *Algorithms* Addison-Wesley. ISBN
978-0-321-57351-3.

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

Knuth, D.A. (2011). *The Art of Computer Programming*.
Addison-Wesley. ISBN 978-0-321-75104-1.

Students hoping to receive a computer science degree from Cambridge are expected to buy, make extensive use of, and keep as reference for their future career, one of the above fundamental textbooks: those not doing so will be severely disadvantaged. The recommended choice is Cormen, Leiserson, Rivest and Stein (CLRS3, starred in the above list) which covers all topics listed and, in spite of its superb quality, is the cheapest: about 35 GBP new for over 1300 pages. The references in the syllabus are to this textbook. The other textbooks listed are excellent additions for further study but might cost more and yet not cover the entire syllabus.