CA313 Algorithms & Complexity

I won't be distributing handouts, but all the notes are available here for you to download and print out. Alternatively, I don't mind if you consult the notes in class on your laptops.

Course Rationale

As a result of this course, students will:

understand the fundementals of complexity theory;
understand the relationship between complexity classes; and
appreciate of the implications of these classes on computation.

A nice summary of what the course is about is:

"Computer Science is no more about computers than astronomy is about telescopes", by Edsger Dijkstra.

Lectures

There are two 1-hour lectures each week: at 15:00 on Mondays in QG27, and at 13:00 on Thursdays, in C114. There are no lab classes or tutorials for this course. You can contact me at away at-thing computing.dcu.ie, or by phone on 5644, or in person in room L201C. The email addresses of the other course lecturers are as follows:

Yanjun Ma at yma at-thing computing.dcu.ie
Anton Bryl at abryl at-thing computing.dcu.ie
Ventzi Zhechev at vzhechev at-thing computing.dcu.ie

We're all located in the CNGL on the top floor of the older School of Computing building, in L201. If you can't get past the swipe card system, contact Eithne McCann, the CNGL Secretary, who's in L217, and she'll let you in.

Assessment

The course is assessed by means of 4 in-class tests (each worth 5%), and an end-of-year exam worth 80%. Given the new academic regulations, the course can be passed by failing the in-class tests or the exam as long as the overall mark for the whole course is 40%. Typically, students in the past have been allowed to discard their worst of the 4 in-class test marks, making each test worth 6.67% in practice.

Indicative Syllabus

The indicative syllabus from the above module spec. includes the following topics:

Sets, relations and functions.
Proofs by induction, breadth-first search and diagonalisation.
Alphabets, words and languages.
Turing machines.
Machines and languages.
Reducibility between languages.
The class P.
Polynomial-time reducibility.
The class NP.
NP-complete languages.
Cook's theorem.
NP-intermediate languages.
The class coNP.
The Boolean hierarchy.
The polynomial hierarchy.
Exponential-time complexity classes.
Space Complexity.
Space complexity classes.
Relations between time and space.
Logarithmic space.
Polynomial space.

We'll see what of this we manage to cover in practice (and in what order) as we go along.

Course Notes

Introduction
Sets
Proofs
Proof by Induction (extra example from class 8/10/07)
Grammars
Turing Machines
Introduction to Algorithms and Complexity Theory
Extra slides not in original handout
Complexity Classes
Heuristics
Space Complexity

Note that Yanjun's notes are available on his website. To access the notes, click "teaching" on the left part of the webpage.

Anton's slides are available on his website.

Class Tests

The class tests and answers will be made available here once each test has taken place. Here are last year's in-class tests, to give you an idea of what to expect.

Past Exam Papers

I understand that the copies kept by the Registry are corrupted. Here are previous exam papers, starting with academic year 2006--07, which was when I began teaching this course:

As you can see, each exam comprises 5 questions, with a free choice of any three questions to be completed.

Questionnaires

I would appreciate it if you took time out to fill in these questionnnaires. They'll only take about 10 minutes each (for subsequent Tests, even less, I think), and the feedback gained will help to improve this subject for future students!

Note that my sendmail script is now working so your responses have started to arrive, for which many thanks!

Useful Texts

Elements of the Theory of Computation, H.R. Lewis & C.H. Papadimitriou, Prentice Hall, 1998 (2nd edition), [511.3/LEW]
Introduction to the Theory of Complexity, D.P. Bovet & P. Crescenzi, Prentice Hall, 1994 [511.3/BOV]
The Theory of Computation, B.M. Moret, Addison-Wesley, 1998, [511.3/MOR]
Models of Computation, J.E. Savage, Addison-Wesley, 1998, [004/SAV]
The New Turing Omnibus, A.K. Dewdney, Freeman & Co., 1989, [004/DEW]

You may also find my notes for CA215 Languages & Computability useful, as this course is a prerequisite for CA313.

Other DCU-internal Information

The official DCU page for this module gives basic information pertaining to this course. There is a separate DCU page entitled Module Resources which may also be useful.

Examples of NP-Complete Problems

Finally, to try to ground the course a bit, I've asked the School of Computing staff for a list of NP-complete problems that they're confronted with in their research areas. So far we have:

Machine Translation (thanks to Hany Hassan).
Task Scheduling: When scheduling mutliple tasks that communicate instantaneously, with precedence relations between them, on 2 processors; then if the tasks have the same computation time there is a polynomial algorithm but if the computation times of the tasks differ, the underlying decision problem becomes NP-complete. If there are 3 processors then it's NP-hard no matter what restriction you put on the tasks, unless all tasks have zero computation and communication time (degenerate solution). Reduces to bin-packing (thanks to David Sinclair).

I'll add to this if and when I hear from colleagues ...

17th November, 2009