## 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.