1. Outline
2. Target audience
3. Implementation
4. Contents


MAT-73006 in the Course Catalog

MAT-73006 Theoretical computer science

Updated: 2015-01-14

A preliminary version of the course outline. Changes possible. (2015)

1. Outline

2. Target audience

The course is meant for nth year undergraduate and graduate students of XXXX.

Prerequisites

3. Implementation

Lectures are given on periods 3 and 4, i.e., the spring semester. Weekly schedule includes 4 h of lectures and 2 h exercises.

The course will consist of exercise assignments and exam. Grading is based on the exam.

There will be lecture slides, which will partially be given on this web page. Exercise assignments will also be given here.

  1. The first exercise (21.1.) (Download PDF) (OK for 2015)
  2. The 2nd exercise (28.1.) (Download PDF) (OK for 2015)
  3. The 3rd exercise (4.2.) (Download PDF)
  4. The 4th exercise (11.2.) (Download PDF)
  5. The 5th exercise (18.2.) (Download)
  6. The 6th exercise (25.2.) (Download PDF)
  7. The 7th exercise (4.3.) (Download PDF)
  8. The 8th exercise (18.3.) (Download PDF)
  9. The 9th exercise (25.3.) (Download PDF)
  10. The 10th exercise (1.4.) (Download
  11. The 11th exercise (15.4.) (Download PDF With answers: (Download PDF)
  12. The 12th exercise (22.4.) (Download pdf)
  13. The 13th exercise (29.4.) (Download pdf)
  14. The 14th exercise (6.5.) (Download
  15. The 15th exercise (13.5.) (Download pdf)

The course lectures and exercises will be based on the book: Introduction to the Theory of Computation, by Michael Sipser (3rd international edition, CENGAGE Learning 2013). Those wishing to pass the course by self-study, should obtain the book by some means.

Course teacher in charge is Henri Hansen.

4. Contents

  1. Regular languages and finite automata
    • Finite automata
    • Nondeterminism
    • Regular expressions
    • Nonregular languages (pumping lemma)
  2. Context-free languages and push down automata
    • Context Free Grammar
    • PushDown Automata
    • Pumping lemma
    • deterministic CFLs and parsing
  3. The Church-Turing thesis
    • Turing Machine
    • Variants of TM
    • Algorithms
  4. Decidability
    • Decidable languages
    • Undeciability
  5. Reducibility
    • Undecidable problems in language theory
    • Undecidable problem
    • Mapping reducibility
  6. Computability theory
    • Recursion theorem
    • Logical theories
    • Turing Reducibility
    • Definition of information
  7. Time complexity
    • Measure of complexity
    • Class P
    • Class NP
    • NP-completeness
  8. Space complexity
    • Savitch's theorem
    • PSPACE
    • PSPACE-completeness
    • L and NL
    • NL-completeness
  9. Intractablitity
    • Hierarchy theorems
    • Relativization
    • Circuit complexity
  10. Advanced Complexity theory
    • Approximation algorithms
    • Probabilistic algorithms
    • Alternation
    • Interactive proof systems
    • Parallel computation
    • Cryptography