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:

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