Fundamentals of Theory of Computation II

Lecture: Monday 8:15 - 9:45, room 2.502
Practice class:
- Monday 10:15 - 11:45, room 1.819
- Tuesday 16:00 - 17:30, room 0.312

Lecturer: Tamás Lukovszki

Content:

Turing machines (TM) as a model of algorithms, Church-Turing thesis. Multi tape, nondeterministic and offline TMs. Computing functions with TMs. Examples for non-recursively enumerable and undecidable languages. Proving undecidability by reduction. Undecidable problems. Complexity classes P, NP, coNP. Polynomial time reduction. NP-completeness. NP-complete problems: SAT and variants, Hamiltonian circuit, travelling salesman problem (TSP), knapsack problem, bin packing problem. Space complexity and complexity classes. Dynamic programming: knapsack problem, longest common subsequence problem. Approximate algorithms: TSP is badly approximable, approximation algorithms for bin packing.

Requirements, evaluation:

0. Mandatory attendance: max. 4 absences are allowed
1. Active partitipation and work in pactice classes: solving and discussing excercises
2. Achieving >=50% on the 10-minute tests at the beginning of the practice classes
3. Successful exams (grade is computed as average of 2 exams)

Important dates:

- midterm test/exam (written): 2025-03-17.
- final test/exam (written): 2025-05-05.
- repeat exam (second trial exam in case of unsuccessful exam, one of the two exams can be retaken): 2025.05.12.

Slides:

-	slides
1. Introduction	PDF

Literature:

- M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.
- M.R. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
- J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson Education Ltd., 2014.