COMP36111: Advanced Algorithms (I), 1st Semester 2018-19
PREREQUISITES
An introductory course on algorithms and data structures, including
understanding basic complexity measures, e.g. the course COMP26120. Parts of the course unit require some mathematical
skills.
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, two areas 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. The complexity-theoretic
hierarchy and fundamental results on relations between complexity
classes.
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.
Learning Outcomes
On successful completion of this course unit:
- You will be able to develop, and reason about the correctness and
performance of, algorithms for string searching and for calculating
over graphs, including polynomial-time algorithms for the marriage
problem and flow-optimization. You will understand the distinction
between linear and polynomial-time tasks, and those with
exponential-time algorithms; tractable and intractable tasks.
- You will have a firm, technical grasp of the notions of time- and
space-complexity classes, including P and NP. You will know about the
most important relationships between familiar complexity classes, and
be aware of many of the major unsolved problems in this area.
- You will understand the notions of reduction and hardness
(and completeness) for a complexity class.
- You will have studied a range of techniques for analysing the
complexity of problems and reasoning with complexity-theoretic
concepts.
- You will have encountered a collection of
well-known problems that are complete for a variety of important
complexity-classes.
Organisation
- This course unit, designed by Dr. Pratt-Hartmann, is taught (for 2018-19 only) by
Dr. Richard Banach.
- The course unit has two forms of assessment:
- Examinations: An end-of-semester examination. The exam counts 75% of the overall course unit mark.
- Exercise sheets:
Two sheets of assessed exercises will be on Blackboard. Your answers will
be marked and these marks contribute with the exam marks to your
overall mark for this course unit. Feedback on your answers will be
given. You may be asked to read up further topics and to write reports
as part of these exercises. The assessed exercises count 25% of the
overall course unit mark.
Examination guidance
In the examination, you will be required to answer 3 questions. The
examination will be structures in such a way as to test the entirity
of the course. It is not a good idea to concentrate on one part of it
and hope that will be enough.
This course has some
past papers online. The syllabus changes somewhat from year
to year (but for 2018-19 will be identical to 2017-18).
Reading List
The recommended reading is
Goodrich, Michael T. and Roberto Tamassia:
Algorithm design and applications, Wiley,
2015. (Available online at the University Library.)
- Lecture 1: G+T Ch 13 to end of 13.4.1, pp. 353--377.
- Lecture 2: G+T Ch 16.
- Lecture 2: G+T Ch 23 to end of 23.3, pp. 651--664.
- Lecture 2: G+T Ch 21 to end of 21.2, pp. 731--745.
Sipser, Michael: Introduction to the theory of computation,
PWS Publishing Company 1997.
The following remarks on the course reading may be helpful.
We recommend that you use the above edition of
Goodrich and Tamassia, which is available as an e-book, and not the older book,
Goodrich, Michael T. and Roberto Tamassia:
Algorithm design: foundations, analysis and internet examples,
Wiley 2002. This latter book is a much less good fit to the course.
Even the new (recommended) version is a little simple for a course at
this level: nevertheless, it is packed with useful information.
Sipser is more on the right level: one thing to watch out for is that
he uses polynomial-time reducibility when talking about
NP-completeness, and switches to log-space reductions when talking
about NL-completeness. This makes some pedagogical sense, but can
cause confusion. In my presentation course, all reductions are
assumed to be in log-space.
Other books which are particularly useful:
Papadimitriou, Christos: Computational Complexity, Addison Wesley, 1994.
Cormen, Thomas L. et al.: Introduction to algorithms, (3rd edition),
MIT Press, 2009.
Useful videos
The following internet videos may be helpful. If you find additional
material you wish to bring to our attention, by all means email the
course leader.
Course unit materials
Slides for the course. Lecture slides will be made available shortly before
each lecture.
There are TWO courseworks for this course.
See the COMP36111 Blackboard website to access
the coursework and to submit your solutions.
Note that we will be applying the
University Policy regarding late submission.
Here are assorted courwork exercises (mostly corresponding to
Coursework B) from the previous three years.
This page was (mostly) created by
Ian Pratt-Hartmann.