CS 3172: Advanced Algorithms, 2nd Semester 2002
This course is officially announced here
Dates (confirmed)
- The course starts on Monday, January 28th and ends on Friday, June 7th.
Each lecture is scheduled from 10--11 am. 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 Feb. 25th/ May 3rd and April 29th/ May 3rd.
- Example classes for Part I are on March 4/8 and for Part II on May 4/8.
- The exam (closed notes, closed book) takes place in Math 1.10 from
9.45 to 11.45 on 22nd May.
Check out new stuff .....
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:
- 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
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
- 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).
- 3. February, 10pm: slides of Chapter 1 modified, also as ps-file available.
- 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.
- 10. February, 5pm: final version of Chapter 1 uploaded,
almost final version of Chapter 2 as well. Preliminary version of Chapter 3.
- 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!).
- 21. February, 8pm: all versions slightly modified. This is it now!
- 22. February, 11pm: The slides for the second part are here.
- 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.
- 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).
- 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:
S
denotes a finite alphabet.
S* denotes the set of all
finite strings that can be built from S. S* also contains the empty string, which is denoted by e (and does not contain any symbols). Thus e is different from the blank #.
A language L is just a subset of S*.
The complement of a language L is itself a language. Namely all elements of S* that are **not** in L.
(Think of the set of primes over the alphabet S = {|}. The complement of it is the set of all composite numbers, plus the empty string e.)
The notions of acceptable or decidable are properties of languages, not of Turing machines.
Suppose you are given a language and you design a Turing machine
to decide it. This Turing machine has a certain complexity.
But the overall complexity of the language might be different:
the complexity of the TM just gives you an upper bound
(you might not have been smart enough
with your machine and there could be another one with a lower complexity).
- 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.