General information
Lecturer: Vitaly Skachek
Teaching staff: Aleksei Ganyukov, Artur Kanoshin, Otto-Cristofer Vanasaun, Kristo Väljako, 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 - 1021 -- 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 - 1025 -- Aleksei Ganyukov (English)
- Mon. 14.15 - 16.00, Narva mnt 18 - 2047 -- Kristo Väljako (Estonian)
- Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Otto-Cristofer Vanasaun (Estonian)
- Tue. 12.15 - 14.00, Narva mnt 18 - 2047 -- Artur Kanoshin (English)
Announcements
- There will be no tutorial classes on Mondat and Tuesday, Fberuary 9 and 10. The first lecture will take place on Friday, February 13, at 12:15.
Old announcements
TBA
Exam dates
- Midterm exam: 17 April 2025, 12:15-13:55, Narva mnt. 18 - 1021 (?)
- Final exam: 29 May 2025, 12:15-13:55, Narva mnt. 18 - 1021
- Midterm exam retake: 29 May 2025, 14:15-15:55, Narva mnt. ???
- Final exam: 12 June 2025, 12:15-13:55, Narva mnt. ???
- Midterm exam retake: 12 June 2025, 14:15-15:55, Narva mnt. ???
- Final exam retake: 19 June 2025, 12:15-13:55, Narva mnt. ???
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, undecidability 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
Part 3: Computability theory
- Turing machines
- Equivalences between different models of Turing machines
- Undecidable problems
- SAT and Cook's theorem
- Examples of NP-complete problems
Image credit: Turing Machine, Tom Dunne, American Scientist, March-April 2002