COMP36111: Advanced Algorithms (I), 1st Semester 2015-16
NEW AND ANNOUNCEMENTS
(Last updated: 27th September 2016)
Listen to the following interesting radio programme
P vs NP.
This course has two pieces of coursework (see below).
We will be applying the
University Policy regarding late submission.
Opportunities for anyone interested in
Theoretical Computer Science by COMP36111:
There are optional
fun problems (sometimes with a nifty solutions, sometimes not)
associated with this course. Anyone who wants to try them is welcome:
Ian Pratt-Hartmann will (usually!) be happy to discuss them if you
have any ideas.
This course is officially announced in the syllabus.
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
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:
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.
- 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
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
- You will have encountered a collection of
well-known problems that are complete for a variety of important
- This course unit is taught by
Dr. Ian Pratt-Hartmann.
- 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 handed out. 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.
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 four
past papers are available. The syllabus changes somewhat from year
to year. I will give detailed guidance on the use of past papers for revision
in the revision lecture.
The recommended reading is
Goodrich, Michael T. and Roberto Tamassia:
Algorithm design and applications, Wiley,
2015. (Available as an online book).
Sipser, Michael: Introduction to the theory of computation,
PWS Publishing Company 1997.
The following remarks on the course reading may be helpful.
- 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.
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.
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 unit materials
Slides for the course. Lecture slides will be made available shortly before
There are just TWO coursework sheets.
Note that we will be applying the
University Policy regarding late submission.
We will be applying the standard University Policy on late submission.
Here are assorted courwork exercises (mostly corresponding to
Coursework B) from the previous three years.
Optional fun problems
Prisoners with party hats
A group of prisoners is facing execution. To make the process more
interesting, they are told that they will lined up (facing along the
line) with coloured hats (red, white or blue) placed on their
heads. Each prisoner will be able to see all the hats of the prisoners
in the line in front of him, but not his own hat, and not the hats of
anyone behind him. (Thus, the first prisoner in the line will be able
to see no hats, and the last prisoner, all but his own.) Starting
from the back, each prisoner in turn must call out a colour (the other
prisoners can hear what he says): if he calls the colour of his own
hat, he is spared; otherwise, he is shot. The prisoners are allowed
to agree on a strategy for what to say before they are stood in
a line and the hats placed on their heads. What strategy will save the
maximum number of prisoners?
No absolute majority
Let S be a multiset of non-negative integers, and let the elements of
S be distributed among k boxes, where k is at least
3. Say that a box contains an 'absolute majority' if the sum of the
numbers from S allocated to it is greater than the sum of all the
numbers from S allocated to all the other boxes. We would like to know
when it is possible for the distribution to be performed in such a way
that no box has an absolute majority. An obvious necessary condition
is that no element of S be greater than the sum of all the other
elements. Show that this condition is also sufficient. What happens
when there are just two boxes?
This is a classic. Let N be a positive integer. There are N housewives, each of
whom has exactly one
piece of gossip to share with the others. They will do this by making
telephone calls. When two housewives speak on the telephone,
they share everything they know. What is the minimum number of
telephone calls required for all the housewives to know all the
The Devil's chessboard
You and a friend are in the company of the Devil. Very shortly,
He will lead you into a room in which there is a standard chessboard.
On each of the 64 squares is a coin with either heads or tails facing
up, in a way that the Devil has seen fit to arrange. Your friend must
wait outside. The Devil will then show you one of the coins and
tell you that this is the Magic Coin. Your friend will not see which
coin the Devil has pointed to. Moreover, the Magic Coin has no visible features by
which it can be identified. In a few moments, your friend will
be led into the room, and he must identify the Magic Coin. You will
not be allowed to
talk to him or give him any other information. All he sees is the chessboard
with the 64 coins arranged on it in some pattern---heads or tails.
However, before your friend enters, you
may flip exactly one of the coins. (Of course, your friend
will not know which coin you have flipped.) Work out a strategy, to be
agreed with your friend before you enter the room, which will
him to identify the Magic Coin.
This page was created by Ian Pratt-Hartmann.