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

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.

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:

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

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 concepts.
- You will have encountered a collection of well-known problems that are complete for a variety of important complexity-classes.

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

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

- Lectures by Robert Sedgwick on Union-Find. (Suggested by Ettore Torti.) Useful for our Lecture 1. Skips the difficult theory, but gives an excellent overview of the algorithms.

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

- Wk 1: Lecture 0 (Intrdoduction), Lecture 1a (Some basic graph algorithms).
- Wk 2: Lecture 1b (Connected components of undirected graphs, fast- and slow-growing functions), Lecture 2 (Just married).
- Wk 3: Lecture 3 (String Matching).
- Wk 4: Lecture 4 (Linear Programming).
- Wk 5: Lecture 5 (Problems, algorithms and complexity measures).
- Wk 7: Lecture 6 (Propositional logic satisfiability).
- Wk 8: Lecture 7 (Hardness and reductions).
- Wk 9: Lecture 8 (Graph-theoretic problems again).
- Wk 10: Lecture 9 (Savitch's Theorem and the Immerman-Szelepcsényi Theorem).
- Wk 12: Lecture 11 (How to pass the exam).

Coursework A:

- Coursework sheet A.
- Solution: my attempt.

Coursework B:

- Coursework sheet B.
- Deadline: 12:00 Thursday, 23rd November, in SSO.
- Solution: my attempt.

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.

- 2011 Section B (solution)
- 2012 Section B (solution)
- 2013 Section A (solution).
- 2013 Section B (solution).
- 2014 Section B (solution).
- 2015 Section B (solution).
- 2016 Section A (solution)
- 2016 Section B (solution)

This page was created by Ian Pratt-Hartmann.