CS 3172: Advanced Algorithms, 2nd Semester 2003

This course is officially announced here

Dates (confirmed)

PREREQUISITES: CS2012.

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

Here are the news, ordered by date

  • 8. February, 9pm: Here are some interesting links: A nice page about Alan Turing, The movie,
    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.
  • 10. February, 8pm: I have been told that neither the pdf nor the postscript files print well. I have therefore modified them and also put a dvi version on the web. It should be easy (with dvips) to produce ps versions from the dvi files (2, 4 or eight pages on one page). Let me know if there are still problems.
  • 11. February, 3pm: Ok, I have now replaced the dvi files by ps-files with ***4 slides on one page***. That should do it.
  • 18. February, 6pm: A student noticed a mistake (or I should say a missing case) on slide 10 in the definition of the next move function. The first line should read " ... if i is greater or equal to 1 ...".
  • 23. February, 11am: Another mistake on slide 78. I have stated "if and only if" but it should be "if" (in all 5 cases).
  • 24. February, 10pm: Finally some students noticed that the reduction I have done (from the language L1={ww^R| w in S^*} to the language L2={ww| w in S^*}) is not correct! Well spotted. The reduction f consisted in transforming the input v into vv^R and I was claiming v is in L1 iff vv^R is in L2. A counterexample is the word v=aba.
    What this reduction really shows is that the language L'={w | w=w^R, w in S^*} is reducible to L2.

  • 11. March, 10am: I got an interesting question after the lecture/clinic yesterday. We had discussed that the number of DTM's for fixed number m of tape symbols and fixed number n of states is finite. But that for unbounded n (with fixed m) the number of DTM's is countable. Then I was asking what happened if we allow infinitely many tape symbols. We noticed that then there would be uncountably many DTM's!!
    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.

  • 15. March, 11pm: Here is a question (from me) relating to the homework we did today. I was asking about the relation between DTIME(134^n) and DTIME((lg n)^n). One student said that the latter class should be contained in the former. Then we discussed that for large enough n, the latter function certainly gives higher values and thus the former class is contained in the latter. But is that really so? Imagine a language L1 which is in DTIME(134^n). Suppose we are given a string (as input to be tested whether it is in L1) of length 16. Then we know that there is a DTM accepting (and also deciding it) in time 134^16. But how can we conclude from this, that it can already be decided in time (lg 16)^16= 4^16 (which must be the case if DTIME(134^n) is contained in DTIME((lg n)^n))?
    Please email your comments!!

  • 16. March, 11am: I have also produced the solutions of the last homework, as we ran out of time at the end. They are here
  • 27. April, 11pm: I got some more questions from students. Please have a look at questions. Also the exercises for the second part are here.
  • 7. May, 9pm: Please note that I (J. Dix) am away from 14-21st May (Conference in Poland).
  • 28. May, 12pm: I added some questions from students and my answers. Good luck for Friday.


    This Page was created by Juergen Dix