Theoretical Computer Science

Full course description

This course explores the theoretical underpinnings of computing by investigating algorithms and programs casted as language recognition problems. The influence of the theory on modern hardware and software system design is demonstrated. The following subjects will be treated: mathematical foundations, alphabets and languages, finite automata and regular languages, Turing machines, acceptance and decidability, recursive functions and grammars, time complexity classes, NP problems, NP-completeness.

This course is an elective: Second year students choose 1 out of the 2 electives in period 4.