COMP36111: Advanced Algorithms (I), 1st Semester 2017-18


NEW AND ANNOUNCEMENTS

(Last updated: 29th September 2017)

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.


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:

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:

  1. 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.
  2. 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.
  3. You will understand the notions of reduction and hardness (and completeness) for a complexity class.
  4. You will have studied a range of techniques for analysing the complexity of problems and reasoning with complexity-theoretic concepts.
  5. You will have encountered a collection of well-known problems that are complete for a variety of important complexity-classes.


Organisation

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


Reading List

The recommended reading is Goodrich, Michael T. and Roberto Tamassia: Algorithm design and applications, Wiley, 2015. (Available as an online book).

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


    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 just TWO coursework sheets. Note that we will be applying the University Policy regarding late submission.

    Coursework A:

    Coursework B:

    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?

    Gossiping housewives

    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 gossip?

    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 allow him to identify the Magic Coin.
    This page was created by Ian Pratt-Hartmann.