demand for greater detailCOMP36111


COMP36111: Advanced Algorithms (I), 1st Semester 2019-20


OFFICE HOURS Wednesdays 11:00--12:00. KB2.38.

There will be no office hours on Wednesday October 23rd.


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 and OBJECTIVES

See syllabus page.

Learning Outcomes

On successful completion of this course unit:

  1. You will be able to undertand standard algorithms for computing strongly connected components in directed graphs, computing components in undirected graphs, computing optimum flows in flow networks, finding maximum matchings in bi-partite graphs, solving the stable marriage problem and matching strings in texts. You will have a good understanding of rates of growth and very rapidly/slowly-growing functions.
  2. You will have a firm technical grasp of time- and space-complexity classes, including PTime and NPTime. 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.


Newsflash

I have had to change my office hours this week (w/c 11th November). Instead of Wednesday at 11:00 I can offer Tuesday at 12:00.

I cannot hold office hours on Wednesday 27th November.


Organisation

Examination guidance

In the examination, you will be required to answer 3 questions. The examination will be structured 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, so revise according to the published syllabus, not just the past papers.


Reading List

The recommended reading is

  • Goodrich, Michael T. and Roberto Tamassia: Algorithm design and applications, Wiley, 2015. (Available online at the University Library.)
  • Sipser, Michael: Introduction to the theory of computation, PWS Publishing Company 1997.

    Detailed guidance on what chapters to read can be find at the end of the lecture slides. 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.


    Course unit materials

    Slides for the course. Lecture slides will be made available shortly before each lecture.

    There are THREE pieces of coursework for this course: one formative and two summative

    Instructions on submission (hard-copy, please) are on the front of each piece of coursework. Note that we will be applying the University Policy regarding late submission.

    My solutions will be posted after the deadlines have passed:

    This page was (mostly) created by Ian Pratt-Hartmann.