## 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 (cancelled)
- Galina Pass: cancelled
- Mozhgan Pourmoradnasseri: cancelled
- TÃ¤hvend Uustalu: cancelled
- Rein Prank: --
- Reimo Palm: contact by email

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

### Online studies during COVID-19 outbreak

**Webinars**

In order to participate, you need to enter the Moodle page of the course, and to press "BigBlueButtonBN" in the upper-left menu.

`Online lectures take place on Fridays, between 12:15-13:45.`

`Online practice session take place on Mondays, at 10:15-11:45.`

### Announcements

`In the case of questions, there are various ways to ask the course staff. We have set up a channel in Slack. There is a forum in Moodle. The private questions could be asked by email.`

##### Old announcements

- An online lecture will take place on March 20, between 12:15-13:45. It will cover the material of Lecture 6 in the lecture notes.
- An online practice session will take place on March 18, at 16:15-17:45. We will cover a material of Tutorial 4. The students from all groups are welcome to join.

If the experiment will be successful, and there will be sufficient interest, we will continue with the webinars in the similar format. - Starting by Monday, March 16, there are no face-to-face meetings. However, all course materials are available online. Specifically, the videos of all the lectures (from a course edition of 2015) are available from "Loengud (Lectures)" submenu. The scripts of the lecture and practice session notes are available on the same page.
- 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.
- 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