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

COMP30172: Advanced Algorithms (2007-2008)

This is an archived syllabus from 2007-2008

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-25,29-32 Lecture 1.4 Mon 10:00 - 11:00 -
Sem 2 w19-25,29-32 Lecture 1.5 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