Course Code : | 1001WETALC |

Study domain: | Computer Science |

Academic year: | 2019-2020 |

Semester: | 2nd semester |

Sequentiality: | - |

Contact hours: | 60 |

Credits: | 6 |

Study load (hours): | 168 |

Contract restrictions: | No contract restriction |

Language of instruction: | Dutch |

Exam period: | exam in the 2nd semester |

Lecturer(s) | Floris Geerts |

At the start of this course the student should have acquired the following competences:

an active knowledge of

general notion of the basic concepts of

specific prerequisites for this course

- competences corresponding the final attainment level of secondary school

an active knowledge of

- Dutch

- English

The textbook for this course is in english.

general notion of the basic concepts of

Elementary mathematics: functions, relations, regular languages.

specific prerequisites for this course

Be familiar with fundamental notions from the theory of formal languages (automata and Turing machines), data structures (trees, graphs) en algorithms (big-O analysis).

Students need to have succesfully completed the courses "Data abstraction and structures", "Machines and Computability" and "Languages and Machines".

- You gain insights in Turing machines and concepts such as space and time complexity of algorithms. More specifically (1) express algorithms as Turning machines; and (2) infer the space and time complexity of algorithms.
- You understand how different complexity classes relate to each other.
- You can distinguish so-called easy and hard computational problems. More specifically, you can place problems in their respective complexity class.
- You gain insight in different complexity classes.
- You can, by means of reductions, establish connections between different problems and establish their hardness and completeness.

The course starts by recalling Turing machines, and one-tape vs multi-tape, deterministic vs non-deterministic machines in particular.

Using Turing machines as our computational model we next consider the concepts of space and time complexity. With regards to time complexity we concentrate on problems that are easy (below or in polynomial time) and those that are intrinsically hard (NP). The role of reduction is crucial in all this and we see many examples of reductions. The Theorem of Cook-Levin, in which the standard NP-complete problem is treated, will be considered. We also detail its proof.

With regards to space complexity, we consider PSPACE, NPSPACE, L and NL en see hard problems for each of these classes. We further see connections between these classes. We treat the Theorem of Savitch and the Theorem of Immerman-Szelepcsenyi (and their proofs).

We conclude with PTIME-completeness.

Class contact teachingLectures Practice sessions

ExaminationWritten examination without oral presentation

Continuous assessmentExercises

Continuous assessment

Slides

Introduction to the Theory of Computation, Michael Sipser

Lectures: Prof. dr. Floris Geerts floris.geerts@uantwerpen.be

Exercise sessions: Stephen.Pauwels@uantwerpen.be