- The course starts on
**Monday, February 3rd**and ends on**Friday, June 7th**.

Each lecture is scheduled from 10--11 am in Lecture Theatre 1.5. We start at 10 am. -
**Part I (Complexity Classes)**is given by Jürgen Dix,**part II (Special Algorithms)**by David Rydeheard. - Each part consists of 8 lectures, plus 2 lectures reserved for example classes.

For each part, one week (2 lectures) is given as additional time for the homeworks.

**This means that there are no lectures on March 3/7 and May 5/9.** -
**Example classes for Part I are on March 10/14 and for Part II on May 12/16.** - The exam (closed notes, closed book) takes place in NN from
NN to NN on NN.

Check out new stuff .....

This module provides an advanced course in algorithms, assuming the student already knows simple algorithms for some of the common computational tasks, and can reason about correctness of algorithms and also derive their complexity. This module covers two related areas: (1) the notion of complexity classes for algorithms and algorithmic tasks, including the famous P/NP problem, and (2) a range of advanced algorithms which illustrate these complexity classes and also the structure, origins and correctness of algorithms.

The module will consist of 18 lectures and the remaining 6 lectures'-worth of time will be devoted to exercises that develop and extend the practical side of the subject. Both the lectured material and the practical exercises are examinable.

On successful completion of this course unit you will:

- understand the general notion of complexity classes (time versus space), including machine models, translations between tasks, and the classification and structure of P/NP/co-NP/PSPACE problems
- be able to develop advanced algorithms over graphs for various algorithmic tasks using a variety of methods of developing algorithms
- be able to argue the correctness of algorithms against specifications
- understand the range of possible algorithmic behaviours of computational tasks and describe example of such behaviours

Hopcroft, J., and Ullman, J.: Introduction to Automata Theory (ISBN 0-201-02988-X) Addison-Wesley 1979. A classic one, but still one of the best for automata theory
and computational complexity. Makes a bit for hard reading, as it is quite formal
and advanced.

Papadimitriou, C. and Steiglitz, K.: Combinatorial Optimization; Algorithms and Complexity, Prentice-Hall, New Jersey, 1982. Also a classic, gives a good picture of P/NP
and the relations to optimization problems.

SEDGEWICK, R. Algorithms in C (ISBN 0-201-51425-7) Addison-Wesley 1990. A general, but good quality, book on algorithms, with some treatment of graph algorithms and computational geometry.

EVEN, S. Graph Algorithms (ISBN 0-91-489421-8) Computer Science Press 1987. A good treatment of graph algorithms. Still in print.

MCHUGH, J.A. Algorithmic Graph Theory. (ISBN 0-13-019092-6) Prentice-Hall International 1990. The best treatment of graph algorithms. Out of print, I believe.

All learning outcomes are assessed through examination, but the practical aspects in outcomes (1), (2) and (3) are developed in the practical exercises in advance of the examinations which will assess these practical aspects as well as the conceptual understanding.

Contribution to Programme Learning Outcomes: A2, B1, B2, B3, C5

Chapter~1: | Turing Machines (4 Lectures) We will introduce the notion of a Turing Machine as our underlying model. This leads to the notion of computable functions and accepted or recognizable languages in general. Various modifications of TMs are discussed and the limit of TMs is shown by presenting the busy beaver function. 1.1 The very definition: TM as a computing device, instantaneous descriptions, (partial) recursive functions, visual Turing. 1.2 Acceptable Languages: TM as a language acceptor, various instances.1.3 Modifications of DTMs: Two-way infinite tape, multi-tape, nondeterministic TM, restrictions.
1.4 Undecidability: The busy beaver.)
Get pdf-Slides Get ps-Slides Get 4 on 1 ps-Slides |

Chapter 2: | Complexity Classes (2 Lectures)We will introduce the most fundamental complexity classes concerning space and time, deterministic and nondeterministic. We also show various speed-up theorems and simple conditions to ensure a class is strictly contained in another one. We finish with some simple relations between various classes. 2.1 Time/Space complexity: Definition of NTIME, DTIME, NSPACE, DSPACE. 1.2 Speed-up: Time speed-up, tape compression, reduction of tapes, reduction of tape alphabet.1.3 Relations between Time and Space: DTIME vs. DSPACE, NTIME vs. DTIME, NSPACE vs. DSPACE.
Get Slides Get ps-Slides Get 4 on 1 ps-Slides |

Chapter 3: | Hierarchies, P/NP (2 Lectures)We introduce the classes PSPACE, NSPACE, P, NP. We also consider polynomial-time reducibility and log-space reducibility and illustrate the notions of completeness and hardness of a problem wrt a complexity class. Various examples are used throughout. 3.1 PSPACE, Reductions: Def. of PSPACE, NSPACE, P, NP. Reducibilities. 3.2 Completeness, Hardness: Problems that are hard or complete for a complexity class.3.3 Examples: Variations of SAT, graph problems, vertex cover.Get Slides Get ps-Slides Get 4 on 1 ps-Slides |

Part 2: | still under construction Get preliminary Slides Get exercises for part 2 |

Turing Test (1), Turing Test (2), Turing Test (3).

I shall keep collecting some questions from students and my answers to them. Might be interesting for you to check from time to time. It is here.

What this reduction really shows is that the language L'={w | w=w^R, w in S^*} is reducible to L2.

Now the question: Why does it make a difference whether we are having infinitely many tape symbols or infinitely many states? If we look at the table describing a DTM, it is completely symmetric!

Well, the answer is: it does not make a difference. If we were to allow infinitely many states, there would be uncountably many DTM's.

There is a huge difference between (1) allowing infinitely many states and (2) allow an unbounded (but finite) number of states.

Please email your comments!!

This Page was created by Juergen Dix |