This is an archived syllabus from 2013-2014
COMP36111 Advanced Algorithms I syllabus 2013-2014
COMP36111 Advanced Algorithms I
Level 3
Credits: 10
Enrolled students: 65
Course leader: Ian Pratt-Hartmann
Additional staff: view all staff
Assessment methods
- 75% Written exam
- 25% Coursework
| Semester | Event | Location | Day | Time | Group |
|---|---|---|---|---|---|
| Sem 1 | Lecture | 1.4 | Fri | 15:00 - 15:00 | - |
| Sem 1 w1-3,5,7-12 | Lecture | 1.4 | Thu | 13:00 - 13:00 | - |
- Programming and Algorithms
Overview
This course unit has two objectives. The first is to introduce the student to a range of advanced algorithms for difficult computational problems, including matching, flow networks and linear programming. The second objective is to ouline the mathematical techniques required to analyse the complexity of computational tasks in general. There are two pieces of assessed coursework, and an exam at the end.Aims
This unit provides an advanced course in algorithms, assuming the student already knows algorithms for common computational tasks, and can reason about the correctness of algorithms and understand the basics of computing the complexity of algorithms and comparing algorithmic performance.
The course focuses on the range of algorithms available for computational tasks, considering the fundamental division of tractable tasks, with linear or polynomial-time algorithms, and tasks that appear to be intractable, in that the only algorithms available are exponential-time in the worst case.
To examine the range of algorithmic behaviour and this fundamental divide, three topics are covered:
- Examining a range of common computational tasks and algorithms available: We shall consider linear and polynomial-time algorithms for string matching tasks and problems that may be interpreted in terms of graphs. For the latter we shall consider the divide between tractable and intractable tasks, showing that it is difficult to determine what range of algorithms is available for any given task.
- Complexity measures and complexity classes: How to compute complexity measures of algorithms, and comparing tasks according to their complexity. Complexity classes of computational tasks, reduction techniques. Deterministic and non-deterministic computation. Polynomial-time classes and non-deterministic polynomial-time classes. Completeness and hardness. The fundamental classes P and NP-complete. NP-complete tasks.
Advanced Algorithms (II): In the second semester a follow-up course unit is available. This course will explore classes of algorithms for modelling and analysing complex systems, as arising in nature and engineering. These examples include: flocking algorithms; optimisation algorithms; stability and accuracy in numerical algorithms.
Syllabus
Part I (up to reading week): Algorithms
- The stable marriage problem
- Basic graph algorithms
- Flow optimization and matching
- Boyer-Moore and Knuth-Morris-Pratt algorithms
- Linear programming
- Integer programming
- Review of Coursework I
Part II (after reading week): Complexity
- Turing Machines and computability (review)
- Problems and complexity classes
- Propositional satisfiability
- Hardness and reductions
- Graph-theoretic problems
- Quantified Boolean Formulas
- Savitch's Theorem
- The Immerman-Szelepcsenyi theorem
- Review of Coursework II
- Revision
Coursework
There will be two coursework exercises:
Coursework I
- Issue date: Thursday 10th October
- Hand-in date: Friday 18th October @ 14:00 (SSO)
- Review: Friday 25th October
Coursework II
- Issue date: Thursday 21st November
- Hand-in date: Friday 29th November @ 14:00 (SSO)
- Review: Friday 6th December
Teaching methods
Lectures
22 lecture course but some lectures will be cancelled to provide time for assessed exercises.
Feedback methods
Two pieces of assessed coursework during the course unit.Study hours
- Lectures (22 hours)
Employability skills
- Analytical skills
- Innovation/creativity
- Problem solving
Learning outcomes
On successful completion of this unit, a student will be able to:
Learning outcomes are detailed on the COMP36111 course unit syllabus page on the School of Computer Science's website for current students.
Reading list
| Title | Author | ISBN | Publisher | Year |
|---|---|---|---|---|
| Computational complexity : a modern approach | Arora, Sanjeev. | 0521424267 (hbk.) :; 9780521424264 (hbk.) : | Cambridge University Press | 2009. |
| Algorithm design and applications | Goodrich, Michael T., author. | 9781119028482 | John Wiley Inc. | 2015 |
| Introduction to the theory of computation | Sipser, Michael. | 9781133187813 | Cengage Learning | c2013. |
Additional notes
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.