Skip to main content

Unit information: Advanced Algorithms in 2014/15

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Advanced Algorithms
Unit code COMS31900
Credit points 10
Level of study H/6
Teaching block(s) Teaching Block 2 (weeks 13 - 24)
Unit director Dr. Clifford
Open unit status Not open




School/department Department of Computer Science
Faculty Faculty of Engineering

Description including Unit Aims

This unit gives an overview of recent advances in the design of algorithms and data structures. These fall into two broad categories.

First are problems, such as pattern matching, succinct data structures and external memory algorithms, for which nearly-optimal solutions are possible. We will discuss a variety of techniques for different problems and different computational models.

Second are problems, such as network optimisation, where sometimes only exponential-time algorithms are known. We will discuss when these problems admit exact efficient solutions, and when only approximation is possible. Some key tools will be randomness and linear programming

Aims: To provide the student with a deep understanding of the most important recent advances in algorithms and data structures and the tools needed to analyse them. This unit should be of particular relevance to anyone with a strong interest in the mathematical aspects of computer science.

Intended Learning Outcomes

On successful completion of this unit the student will

  • Have a solid understanding of the most important recent advances in algorithms and data structures.
  • Be able to apply sophisticated analysis techniques to measure the time and space complexity of algorithms and also prove their correctness.
  • Understand a variety of data structures and their applications.

Know which combinatorial or convex optimisation problems can be solved efficiently, which cannot and when good approximations are possible.

Teaching Information

20 hours of lectures, a further 80 hours are nominally set aside for coursework, private study, etc.

Assessment Information

Coursework 30% and examination 70%

The coursework will test and extend knowledge of the material taught in roughly the first half of the unit. It will be a mixture of questions which test the students' understanding of the data structures and algorithms taught and also questions which ask the student to show familiarity with the latest advances in specific aspects of the material."

Reading and References

  • Introduction to Algorithms – Cormen, Leiserson, Rivest, Stein
  • Algorithms - S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani