### General information

**Lecturer:** Vitaly Skachek **Teaching staff:** Raiko Marrandi, Teele Tars, Hans Kristjan Veri, Kristo Väljako, Daniel Würsch, Rein Prank, Reimo Palm **Language of instruction:** lectures are in English, practice sessions are in English and Estonian **Lectures:**

- Fri. 12.15 - 14.00, Narva mnt 18 - 1037 -- Vitaly Skachek (English)

**Tutorials:**

- Mon. 10.15 - 12.00, Narva mnt 18 - 1008 -- Raiko Marrandi (Estonian)
- Mon. 12.15 - 14.00, Narva mnt 18 - 2047 -- Hans Kristjan Veri (English)
- Mon. 14.15 - 16.00, Narva mnt 18 - 2047 -- Teele Tars (Estonian)
- Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Kristo Väljako (Estonian)
- Tue. 12.15 - 14.00, Narva mnt 18 - 2047 -- Daniel Würsch (English)

### Announcements

- The retake of the final exam will take place on Friday, June 16th, between 12:15-13:55, in room Delta 1019. The exam will be held in person (no online option is planned). The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)

### Old announcements

- The second final exam will take place on Friday, June 9th, between 12:15-13:55, in room Delta 1018. The retake of the midterm exam will take place on June 9th between 14:15-15:55 in room Delta 1018. Both exams will be held in person (no online option is planned). The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
- The final exam will take place on Friday, May 26th, between 12:15-13:55, in room Delta 1020. The retake of the midterm exam will take place on May 26th between 14:15-15:55 in room Delta 1017. Both exams will be held in person (no online option is planned). The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
- The lecture on May 19th will take place in room 1020 in Delta, and not in a regular place.
- On Monday, May 1st, there will be no practice sessions. There are three options:
**(1)**To attend the practice session on Tuesday, May 2nd:

Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Kristo (Estonian);

Tue. 12.15 - 14.00, Narva mnt 18 - 2047 -- Daniel (English);**(2)**To watch the video recording of the class;**(3)**To read the notes of Week 12.

Vitaly will have a special reception hour on Tuesday 15:00-16:00, room 3074 in Delta, where you can ask anything related to the material of the last two weeks.

- The midterm exam will take place on Friday, April 14th, between 12:15-13:55, in room Delta 1037 (the regular lecture time and place). The exam will be held in person (no online option is planned). The answers are to be written on the paper. The duration of the exam is 1 hour and 40 minutes. Any written and printed materials are allowed in the exam (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
- There will be no lecture on April 7. Please see the last example in the material of Lecture 8 (in Moodle).
- There will be no lecture on February 24. We have a video recording of the same lecture from the last year available in Moodle. It is called "Recording of Lecture 3 from the last year". Please watch it before the practice sessions, or, alternatively, please read the lecture notes of Week 3 up to the "Proof" or "Tõestus" in page 5.
- There will be no tutorials (practice sessions) on February 6-7. The first tutorials will take place on February 13-14. The first lecture will take place on February 10.

### Exam dates

*Midterm exam*: April 14th at 12:15-13:55, Delta 1037*Final exam*: May 26th at 12:15-13:55, Delta 1020*Midterm exam retake*: May 26th at 14:15-15:55, Delta 1017*Final exam*: June 9th at 12:15-13:55, Delta 1018*Midterm exam retake*: June 9th at 14:15-15:55, Delta~~1019~~1018*Final exam retake*: June 16th at 12:15-13:55, Delta 1019

### Literature

- Michael Sipser,
*Introduction to the Theory of Computation* - Jiri Matousek and Jaroslav Nesetril,
*An Invitation to Discrete Mathematics*

### Course description

This is a second year bachelor-level introductory course into the theory of computer science. The course will emphasize mathematical foundations of computer science, and will focus on computational models, their analysis and formal proofs. While theory of computer science is very important in practice, this course will **not** focus on implementations and programming.

In the first four weeks we will briefly cover basic counting techniques in combinatorics. Then, several weeks will be devoted to the automata theory. The second half of the semester will be devoted to computational models, Turing machines and NP-hardness.

### Grading policy

There will be a number of homework assignments, mid-term and final exams. The homework assignments and exams are evaluated on the scale 0-100 (extra bonus points are possible). The final grade is taken as a weighted average of homeworks and exams, and translated into "A"-"F" scale. The composition of the grade is: homeworks (20%), mid-term exam (40%) and final exam (40%). The homeworks will mainly contain questions of theoretical and mathematical nature, and typically will not include programming tasks.

### Syllabus

The following is a preliminary list of topics (some deviations from this list are possible):

#### Part 1: Enumerative combinatorics

- Permutations and combinations
- Newton’s binomial theorem
- Inclusion-exclusion principle

#### Part 2: Automata theory

- Deterministic and non-deterministic finite automata
- Regular expressions and regular languages
- Context-free languages

#### Part 3: Computability theory

- Turing machines
- Undecidable problems
- Equivalences between different models of Turing machines
- SAT and Cook's theorem
- Examples of NP-complete problems

Image credit: Turing Machine, Tom Dunne, American Scientist, March-April 2002