Skip to navigation | Skip to main content | Skip to footer

COMP30172: Advanced Algorithms (2009-2010)

This is an archived syllabus from 2009-2010

Advanced Algorithms
Level: 3
Credit rating: 10
Pre-requisites: COMP20012 or INFO20006
Co-requisites: No Co-requisites
Duration: 11 weeks in second semester
Lectures: 20 in total, plus 4 lectures of practical exercises
Lecturers: Howard Barringer, David Rydeheard
Course lecturers: Howard Barringer

David Rydeheard

Additional staff: view all staff
Sem 2 w19-26,30-33 Lecture 1.4 Mon 10:00 - 11:00 -
Sem 2 w19-26,30-33 Lecture 1.3 Fri 12:00 - 13:00 -
Assessment Breakdown
Exam: 100%
Coursework: 0%
Lab: 0%
Degrees for which this unit is optional
  • Artificial Intelligence BSc (Hons)


This unit provides an advanced course in algorithms, assuming the student already knows simple algorithms for common computational tasks, and can reason about the correctness of algorithms and derive their complexity.

The course unit covers (1) a range of advanced algorithms in areas such as string searching and graph algorithms and their applications, (2) the notion of complexity classes for algorithmic tasks, completeness and hardness, and proofs by reduction, and (3) probabilistic techniques and algorithms.

The range of advanced algorithms will illustrate the complexity classes and also the structure, origins and correctness of algorithms.

Learning Outcomes

On successful completion of this course unit you will:
Understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction. You will also have seen how to show tasks are NP-complete.
Be able to develop, and reason about the correctness and performance of algorithms, in particular for string searching and graph manipulation, and understand how graph algorithms arise in automated verification.
Have studied a range of probabilistic algorithms, understand the key issues involved, and be able to use probabilistic techniques in algorithms.

Assessment of Learning outcomes

All learning outcomes are assessed through examination, but the practical aspects in outcomes (1), (2) and (3) are developed in the practical exercises in advance of the examinations which will assess these practical aspects as well as the conceptual understanding.

Contribution to Programme Learning Outcomes

A2, B1, B2, B3, C5.



Overview, organisation, background, issues.

String Searching Algorithms

Including preconditioning for Boyer-Moore and Knuth-Morris-Pratt type algorithms, and Harrison hashing and applications in web search engines.

Graph Algorithms

Review of graphs, Graph Traversal, DFS algorithms, Path Finding. Other computational tasks on graphs,.


Automated Verification via finite and infinite word automata.

Complexity Classes

Polynomial Time and Space, NP Time and Space, Completeness and Hardness, SAT and Cook's Theorem, 2-SAT. Proofs of NP-Completeness for Computations on Graphs.

Randomised and Probabilistic Algorithms

Random number generators. Applications of randomisation: Sherwood, Las Vegas , Monte Carlo algorithms.

Summary, Revision and Exam

2 exercise sessions. 2 revision sessions

Reading List

Title: Graph algorithms
Author: Even, Shimon
ISBN: 0914894218
Publisher: Computer Science Press
Year: 1979

Title: Fundamentals of algorithmics
Author: Brassard, Gilles and Paul Bratley
ISBN: 0133350681
Publisher: Prentice Hall
Year: 1996

Title: Introduction to automata theory, languages, and computation (3rd edition)
Author: Hopcroft, John E., Rajeev Motwani, and Jeffrey D.Ullman
ISBN: 9781292039053
Publisher: Pearson Education
Edition: 3rd
Year: 2014

Title: Introduction to the theory of complexity
Author: Bovet, Daniel Pierre and Pierluigi Crescenzi
ISBN: 0139153802
Publisher: Prentice Hall
Year: 1993

Title: Algorithms in Java (3rd edition): part 5: graph algorithms
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361213
Publisher: Addison Wesley
Edition: 3rd
Year: 2004
Parts 1-4 (fundamentals, data structures, sorting, searching) are one separate volume: ISBN 0201361205

Title: Computer algorithms: introduction to design and analysis (3rd edition)
Author: Baase, Sara and Allen van Gelder
ISBN: 0201612445
Publisher: Addison Wesley
Edition: 3rd
Year: 2000

Title: Algorithms in Java (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361205
Publisher: Addison Wesley
Edition: 3rd
Year: 2003
Part 5 (graph algorithms) is separate volume: ISBN 0201361213

Title: Randomized algorithms
Author: Motwani, Rajeev and Prabhakar Raghavan
ISBN: 0521474655
Publisher: Cambridge University Press
Year: 1995

Title: Algorithmic graph theory
Author: McHugh, James A.
ISBN: 0130236152
Publisher: Prentice-Hall
Year: 1990

Title: Model checking
Author: Clarke, Edmund M., Orna Grumberg, and Doron A.Peled
ISBN: 0262032708
Publisher: MIT Press
Year: 2000

Title: Combinatorial optimization: algorithms and complexity
Author: Papadimitriou, Christos H. and Kenneth Steiglitz
ISBN: 9780486402581
Publisher: Dover
Year: 2000