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.

See syllabus page.

On successful completion of this course unit:

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

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.

- This course unit is designed and presented by Dr. Pratt-Hartmann.
- The course unit has two forms of assessment: coursework and examination. See the syllabus page for details. The object of all the coursework (formative and summative) is to help the student understand the style and level of mathematical detail needed to pass the examination.

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.

The recommended reading is

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:

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

- Wk 1: Lecture 0 (Intrdoduction and course organization),
- Wk 1: Lecture 1 (Getting started).
- Wk 2: Lecture 2 (Almost linear).
- Wk 3: Lecture 3 (Flow).
- Wk 4: Lecture 4 (Just married!).
- Wk 4: Lecture 5 (Searching strings).
- Wk 5: Lecture 6 (The machine stops).
- Wk 7: Lecture 7 (Try to be logical ...).
- Wk 8: Lecture 8 (How hard can this be?).
- Wk 9: Catch-up and preparation for final coursework exercise.
- Wk 10: Lecture 9 (If you're so clever, why can't you ...?).
- Wk 11: Lecture 10 (For completeness' sake!).
- Wk 12: Lecture 11 (His last bow); Lecture 12 (How to pass the exam).

- 36111-cwk1-F-Formulating arguments: click here for my solutions.
- 36111-cwk2-S-Exercises A: click here for my solutions. Mean 14.35, median 15.5, mode 19, standard deviation 5.01.
- 36111-cwk3-S-Exercises B: click here for my solutions. Mean 14.6, median 16, mode 16, standard deviation 4.51. The class did very well on a tough assignment.

My solutions will be posted after the deadlines have passed:

- Watch this space.
- Watch this space.
- Watch this space.