Introduction to Complexity and Computability

Introduction to Complexity and Computability - practicals

Winter term 2019/20

Practicals from the previous year: winter term 2018/19 EN.
Place: Tuesdays 10:40-12:10, room S1, even weeks in semester (i.e. odd weeks in calendar).
Teacher: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Course information: 2/1 Zk/Z NTIN090 in SIS, on webpage of the lecturer

Exercises and Homeworks
Here will be a list of exercises and homeworks from each practicals.

Session 1, 08. 10. 2019: Turing machines.
Session 2, 22. 10. 2019: Modifications of Turing machines, (partially) decidable languages.
Session 3, 05. 11. 2019: Enumeration of (partially) decidable languages, reducibility.
Session 4, 19. 11. 2019: Reducibility, s-m-n theorem, Rice's theorem.
Session 5, 03. 12. 2019: Basic complexity classes.
Session 6, 17. 12. 2019: Relations between complexity classes. Polynomial reductions.
Session 7, 07. 01. 2020: NP-completeness, approx. algorithms.

Extra homeworks
The (updated) list of extra homeworks is here.

Evaluation
Evaluation will be based on points for homeworks. Each practicals, several problems will be assigned for homework totally for about 3 points. The deadline for each homework will be the next practicals. You will need at least 12 points, that is about 2/3 points from the first 6 practicals. Additional points will be available for homework assigned on the last (7th) practicals on Jan 7th.

Consultation hours
Tuesdays 10:40-12:10 in odd weeks, room 305, or by an email appointment.

Note
These practicals are primarily for students in English study programs. Students in Czech study programs are welcome to enroll these practicals, up to the capacity of the room S1.