## Introduction to Complexity and Computability - practicals

*Winter term 2018/19*
**Place:** Thursday 15:40-17:10, room S1, odd weeks in semester (i.e. even 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, 04. 10. 2018: Turing machines.
- Session 2, 18. 10. 2018: Modifications of Turing machines, (partially) decidable languages.
- Session 3, 01. 11. 2018: Enumeration of (partially) decidable languages, reducibility.
- Session 4, 15. 11. 2018: Reducibility, s-m-n theorem, Rice's theorem.
- Session 5, 29. 11. 2018: Basic complexity classes.
- Session 6, 13. 12. 2018: Relations between complexity classes.
- Session 7, 03. 01. 2019: Polynomial time reducibility, 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 2/3 points from the first 6 practicals to obtain the credit, that is 12 points. Additional points will be available for homework assigned on the last (7th) practicals.

**Consultation hours**

Thursday 15:40-17:10 in even weeks, room 305, or after practicals in odd weeks.

**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. My practicals from previous year are available in Czech here.