## Introduction to Theoretical Computer Science

**Instructor:** Vitaly Skachek **Assistants:** Yauhen Yakimenka, Reimo Palm **Lecture:** Thursday 12:15 - 14:00, J. Liivi 2-405 **Practice:** Monday 12:15-14:00, J. Liivi 2-403 **Office hours:**

- Vitaly Skachek: Thursday 10:15-11:15 and 15:15-16:15, J. Liivi 2-216 (or by appointment)
- Yauhen Yakimenka: Monday 16:15-17:45, J. Liivi 2-218 (or by appointment) <<< when at the door, knock and just enter without waiting
- Reimo Palm: Tuesday 15:00-17:00, J. Liivi 2-336 (or by appointment)

**Language of instruction:** English **Note:** The students in Computer Science curriculum, who started their Bachelor studies in Fall 2014/2015, are allowed to choose one course from ** MTAT.05.125 Introduction to Theoretical Computer Science** and

**as a part of the degree requirements. In a case of doubt, please check your eligibility with the study coordinator.**

*MTAT.06.008 Artificial Intelligence I*### Final exam

The **second retake** of the final exam will take place on **Wednesday, February 3rd**, between 15:15-17:15, room 202. Any printed and written material can be used. No electronic devices are allowed at the exam. In order to participate, you need to send an email to Vitaly as soon as possible, and to register for the exam officially.

The final exam took place on **Thursday, December 17th**.

The retake of the final exam took place on **Thursday, January 14th**.

### Midterm exam

The midterm exam took place on **Monday, November 9th**.

A retake of the midterm exam took place on **Thursday, December 17th**.

A second retake of the midterm exam took place on **Thursday, January 14th**.

You can see your obtained points here: http://kodu.ut.ee/~yauhen/teaching/intro-tcs/points.cgi

### Literature

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

### Course description

This is a bachelor-level introductory course into the theory of computer science. The course will emphasize mathematical foundations of computer science, and will focus on analysis and proofs. The course will **not** focus on implementations and programming.

In the first few weeks we will briefly cover basic counting techniques in combinatorics. Then, approximately half of the semester 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 (30%), mid-term exam (30%) 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