Course pages 2017–18
Algorithms
Principal lecturers: Dr Robert Harle, Dr Damon Wischik
Taken by: Part IA CST 50%, Part IA CST 75%, Part IA NST, Part I PBS
Past exam questions
No. of lectures and practical classes: 24 + 3 (NST and PBST students take 1 practical)
Suggested hours of supervisions: 6 to 8
Prerequisite courses: Foundations of Computer Science,
Object-Oriented Programming
This course is a prerequisite for: Artificial Intelligence, Complexity
Theory, Further Graphics, Prolog and the following Part II courses: Advanced
Algorithms and Machine Learning and Bayesian Inference
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 and O-notation. Trivial
sorting algorithms of quadratic complexity. Review of merge sort and
quicksort, understanding their memory behaviour on statically
allocated arrays. Heapsort. Stability. Other sorting methods
including sorting in linear time. Median and order statistics.
[Ref: CLRS3 chapters 1, 2, 3, 6, 7, 8, 9] [about 4 lectures]
- Strategies for algorithm design.
Dynamic programming, divide and conquer, greedy algorithms and other
useful paradigms.
[Ref: CLRS3 chapters 4, 15, 16] [about 3 lectures]
- Data structures. Primitive 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: CLRS3 chapters 6, 10, 11, 12, 13, 18] [about 5 lectures]
- Graph algorithms. Graph representations. Breadth-first and
depth-first search. Topological sort. Minimum spanning tree. Kruskal
and Prim algorithms. Single-source shortest paths: Bellman-Ford and
Dijkstra algorithms. All-pairs shortest paths: matrix
multiplication and Johnson’s algorithms. Maximum flow:
Ford-Fulkerson method, Max-Flow Min-Cut Theorem. Matchings in bipartite graphs. [Ref: CLRS3
chapters 22, 23, 24, 25, 26] [about 7 lectures]
- Advanced data structures. Binomial heap. Amortized analysis:
aggregate analysis, potential method. Fibonacci heaps. Disjoint sets.
[Ref: CLRS3 chapters 17, 19, 20, 21] [about 4 lectures]
- 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 thorough understanding of several classical algorithms
and data structures;
- be able to analyse the space and time efficiency of most
algorithms;
- 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 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.