CS 3172: Advanced Algorithms, 2nd Semester 2002


This course is officially announced here


Dates (confirmed)


PREREQUISITES: CS2011.


AIMS


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.


Learning Outcomes


On successful completion of this course unit you will:

  1. 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
  2. be able to develop advanced algorithms over graphs for various algorithmic tasks using a variety of methods of developing algorithms
  3. be able to argue the correctness of algorithms against specifications
  4. understand the range of possible algorithmic behaviours of computational tasks and describe example of such behaviours


Reading List


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.


Assessment of Learning Outcomes


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


Syllabus

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


Here are the news, ordered by date
  1. 28. January, 9pm: slides of Chapter 1 modified.
    Here are some interesting links:
    A nice page about Alan Turing, The movie,
    Turing Test (1), Turing Test (2), Turing Test (3).
  2. 3. February, 10pm: slides of Chapter 1 modified, also as ps-file available.
  3. 5. February, 6pm: slides of Chapter 1 and 2 modified.
    A student asked in the lecture about a visual representation of a nondeterministic TM (like in visual Turing for deterministic machines). There is indeed one, namely Turing's world Turings world. Unfortunately, it only works for the Mac.
    Here is a theater play about Alan Turing Breaking the code.
  4. 10. February, 5pm: final version of Chapter 1 uploaded, almost final version of Chapter 2 as well. Preliminary version of Chapter 3.
  5. 12. February, 10pm: final version of Chapters 2 and 3 uploaded.

    Make sure you are starting to work on the homeworks, if you have not already done so.
    Find out about your problems (if you have some) in solving the exercises.
    Feel free to email me (Jürgen Dix) so that I am getting a feeling of your difficulties and
    we can discuss them in the first week of March.


    Once you have understood all the homeworks, you should have no problem in passing the exam
    (well, this comes without any warranty!).
  6. 21. February, 8pm: all versions slightly modified. This is it now!
  7. 22. February, 11pm: The slides for the second part are here.
  8. 22. April, 12pm: A student noticed a typo in the Copy machine in Example 1.1, slide 16 (shame on all other students: you should have noticed it as well!): the first entry in the column for q4 should read (q5,1,L).

    The exercises for the second part are here.
  9. 10. May, 23pm:In the session today the following question came up: Are there any problems that are not in NP?
    Both David and I did not immediately remember a nice example. After some contemplation, we came up with the following.

    The towers of Hanoi
    Input: the start configuration of the towers of Hanoi (n discs, 3 pegs as usual).
    Output: The sequence of moves, that solves the problem (moving all discs from the first peg to the third).

    It can be shown that this problem is in EXPTIME (i.e. it requires exponential time).

    A problem that is even more complex is one that requires EXPSPACE, i.e. the tape needed to solve it
    is exponential (and hence the time needed is also exponential). Such a problem is determining
    the truth of formulae in Presburger arithmetic.

    Presburger Arithmetic
    Input: A sentence involving the constants 0, 1, 2, as well as addition +, comparison >, quantifiers and
    the usual connectives. E.g. "for all y>0 there is a x with 1+x=y "(this is a true statement). Or "for all x: x+x=x+x+x" (this is false).
    Output: Yes (if the sentence is true) or No (if the sentence is false).



  10. 15. May, 6pm: Here are some last minute clarifications, based on the questions and comments I got in the last days. Please note the following:




  11. 16. May, 23pm: I have collected some questions from students and my answers to them. Might be interesting for you to check. It is here.


This Page was created by Juergen Dix