## Introduction to Theoretical Computer Science

**Instructor:** Vitaly Skachek **Assistants:** Galina Pass, Mozhgan Pourmoradnasseri, TÃ¤hvend Uustalu, Rein Prank, Reimo Palm **Lecture:** Friday 12:15 - 14:00, Narva mnt. 18 - 1021 **Practice sesssions:**

Mon. 10.15 - 12.00, Narva mnt. 18 - 1022 -- Mozhgan (in English)

Mon. 12.15 - 14.00, Narva mnt. 18 - 2045 -- Mozhgan (in English)

Mon. 14.15 - 16.00, Narva mnt. 18 - 2034 -- TÃ¤hvend (in Estonian)

Tue. 10.15 - 12.00, Narva mnt. 18 - 2047 -- Galina (in English)

Wed. 16.15 - 18.00, Narva mnt. 18 - 2045 -- Mozhgan (in English)
**Office hours:**

- Vitaly Skachek: Friday 10:00-12:00, Narva mnt. 18 - 3074
- Galina Pass: TBA
- Mozhgan Pourmoradnasseri: TBA
- TÃ¤hvend Uustalu: TBA
- Rein Prank: TBA
- Reimo Palm: contact by email

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

### Announcements

`There are no classes on February 24th (Monday), the Independence Day. In order to keep all the practice session groups synchronized, the practice sessions on February 25th and 26th are also cancelled. The lecture on February 28th takes place as usual.`

##### Old announcements

- There will be no practice sessions in the first week of the semester (February 10-12). The first lecture will take place on Friday, February 14.

### Exam information

*Midterm exam*: April 17, room 1021, approximately 12:15-14:00 (lecture time)*Final exam*(first date): May 29, room 1021, approximately 12:15-14:00 (lecture time)*Final exam*(second date): June 12, room 1021, approximately 14:15-16:00*Final exam retake*: June 19, room 1008, approximately 12:15-14:00

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