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

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
Timetable
SemesterEventLocationDayTimeGroup
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)

Aims

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.

Syllabus

Introduction


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,.

Application


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
Edition:
Year: 1979


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


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


Title: Introduction to automata theory, languages, and computation (2nd edition)
Author: Hopcroft, John E., Rajeev Motwani, and Jeffrey D.Ullman
ISBN: 0201441241
Publisher: Addison Wesley
Edition: 2nd
Year: 2001


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
Edition:
Year: 1995


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


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


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