### General information

**Lecturer:** Vitaly Skachek **Teaching staff:** Kristo Väljako, Artur Aleksander Kanošin, Hans Kristjan Veri, Kristiina Oksner, Teele Tars, 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 - 2047 -- Kristo Väljako (Estonian)
- Mon. 12.15 - 14.00, Narva mnt 18 - 2047 -- Artur Aleksander Kanošin (English)
- Mon. 14.15 - 16.00, Narva mnt 18 - 2047 -- Hans Kristjan Veri (Estonian)
- Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Kristiina Oksner (Estonian)
- Tue. 12.15 - 14.00, Narva mnt 18 - 2047 -- Teele Tars (Estonian)

### Announcements

- The second final exam will take place on
**June 14th**between**12:15-13:55**in room**Delta 1037**. The second retake of the midterm exam will also take place on**June 14th**between**14:15-15:55**in room**Delta 1022**.

Both exams will be held in person. 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 own hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)

### Old announcements

- The final exam on
**May 31st**, between**12:15-13:55**, in room**Delta 1037**. The retake of the midterm exam will take place on**May 31st**, between**14:15-15:55**, in room**Delta 2048**.

Both exams will be held in person. 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 midterm exam will take place on Friday, April 19th, between 12:15-13:55, in room Delta 1037. 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.)
- The lecture on February 23rd will take place according to the regular schedule (12:15-14:00).
- There will be no practice sessions (tutorial) on February 12th and 13th. The first lecture will take place on February 16th.

### Exam dates

*Midterm exam*: April 19th at 12:15-13:55, Delta 1037*Final exam*: May 31st at 12:15-13:55, Delta 1037*Midterm exam retake*: May 31st at 14:15-15:55, Delta 2048*Final exam*: June 14th at 12:15-13:55, Delta 1037*Midterm exam retake*: June 14th at 14:15-15:55, Delta 1022*Final exam retake*: June 21st at 12:15-13:55, Delta 2045

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