Computability, Decidability, and Complexity
Fall 2026
Course Information
Discipline Sheet: CDC_EN / CDC_RO.
Course Goal: The course is intended for undergraduate students. Its purpose is to clarify the power and limitations of algorithmic computation. Specifically, we will try to answer questions such as:
- What is an algorithm?
- What are the limits of computation?
- Are there problems that no algorithm will ever solve?
- Are there problems that cannot be solved efficiently?
- How do we classify problems according to the difficulty of solving them?
These are all closely related to practical issues such as compiler design, program checking, computational intractability, approximability, and cryptography.
Prerequisites: The course requires no special prior knowledge. However, an acquaintance with the o, O, Ω, and Θ notation, as introduced in this site’s “Algebraic Foundations of Computer Science,” may be helpful.
Readings: Many excellent textbooks on computability, decidability, and complexity exist. However, the course follows its own path, so each lecture will end with a bibliographic list and study recommendations. The recommended literature will be easily accessible to all students.
Lectures, office hours, exam sessions:
- Teaching weeks and examination sessions: see the university calendar;
- Lectures and seminars: check the faculty-set schedule;
- Office hours: Wednesday, 15-16, in C301;
- Lecture and seminar materials are available here.
Grading:
- The evaluation is based on active class participation through exercise solving (40%), continuous written assessment (45%), and a written test (15%);
- Please note that you can retake only the tests during the re-examination session!
Course Staff
Instructor: Prof. Dr. Ferucio Laurențiu ȚIPLEA, Department of Computer Science, “Alexandru Ioan Cuza” University of Iași, Romania, e-mail: ferucio dot tiplea at uaic dot ro or fltiplea at gmail dot com.
Course Syllabus and Seminar Guide
Lecture and seminar materials are available here