General information
Lecturer: Vitaly Skachek
Teaching staff: Kristo Väljako, Artur Aleksander Kanošin, Hans Kristjan Veri, Kristiina Oksner, Teele Tars, Rein Prank, 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 - 1037 -- 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 - 2047 -- Artur Aleksander Kanošin (English)
- Mon. 14.15 - 16.00, Narva mnt 18 - 2047 -- Hans Kristjan Veri (Estonian)
- Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Kristiina Oksner (Estonian)
- Tue. 12.15 - 14.00, Narva mnt 18 - 2047 -- Teele Tars (Estonian)
Announcements
- The retake of the final exam will take place on June 21st between 12:15-13:55 in room Delta 2045.
The exam will be held in person. The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your own hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
Old announcements
- The second final exam will take place on June 14th between 12:15-13:55 in room Delta 1037. The second retake of the midterm exam will also take place on June 14th between 14:15-15:55 in room Delta 1022.
Both exams will be held in person. The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your own hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.) - The final exam on May 31st, between 12:15-13:55, in room Delta 1037. The retake of the midterm exam will take place on May 31st, between 14:15-15:55, in room Delta 2048.
Both exams will be held in person. The answers are to be written on the paper. The duration of each exam is 1 hour and 40 minutes. Any written and printed materials are allowed (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.) - The midterm exam will take place on Friday, April 19th, between 12:15-13:55, in room Delta 1037. The exam will be held in person (no online option is planned). The answers are to be written on the paper. The duration of the exam is 1 hour and 40 minutes. Any written and printed materials are allowed in the exam (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
- The lecture on February 23rd will take place according to the regular schedule (12:15-14:00).
- There will be no practice sessions (tutorial) on February 12th and 13th. The first lecture will take place on February 16th.
Exam dates
- Midterm exam: April 19th at 12:15-13:55, Delta 1037
- Final exam: May 31st at 12:15-13:55, Delta 1037
- Midterm exam retake: May 31st at 14:15-15:55, Delta 2048
- Final exam: June 14th at 12:15-13:55, Delta 1037
- Midterm exam retake: June 14th at 14:15-15:55, Delta 1022
- Final exam retake: June 21st at 12:15-13:55, Delta 2045
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 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
- 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
Image credit: Turing Machine, Tom Dunne, American Scientist, March-April 2002