## Introduction to Theoretical Computer Science

**Instructor:** Vitaly Skachek **Assistants:** Eldho Thomas, Ivo Kubjas, Mozhgan Pourmoradnasseri, Ãœlo Reimaa, Rein Prank, Reimo Palm **Lecture:** Monday 12:15 - 14:00, J. Liivi 2-111 **Practice sesssions:**

Tuesday 08:15 - 10:00, J. Liivi 2-202 and/or J. Liivi 2-206 -- Eldho (in English)

Tuesday 14:15 - 16:00, J. Liivi 2-207 -- Ivo (in Estonian)

Wednesday 08:15 - 10:00, J. Liivi 2-405 -- Mozhgan (in English)

Wednesday 14:15 - 16:00, J. Liivi 2-207 -- Mozhgan (in English)

Wednesday 16:15 - 18:00, J. Liivi 2-405 -- Ãœlo (in Estonian) `Note: two groups of practice sessions on Tuesday 08:15-10:00 will be joined together, and the joint practice session class will take place in J. Liivi 2-202.`

**Office hours:**

- Vitaly Skachek: Monday 16:00-17:00, Ãœlikooli 17-224 (Paabel)
- Eldho Thomas: Wednesday 14:00-15:00, Ãœlikooli 17-225
- Ivo Kubjas: Monday 16:00-17:00, Ãœlikooli 17-225
- Mozhgan Pourmoradnasseri: Tuesdays 15:00-16:00, Ãœlikooli 17-327
- Ãœlo Reimaa: Wednesday 14:00-15:00, Ãœlikooli 17-225
- Reimo Palm: contact by email

**Language of instruction:** lectures are in English, practice sessions are in English/Estonian

### Literature

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

### Course description

This is a mandatory 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 homeworks, the mid-term and final exams. The homeworks and exams are evaluated on the scale 0-100. 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