General information
Lecturer: Vitaly Skachek
Teaching staff: Raido Everest, Karan Khathuria, Thamara Luup Carvalho, Henri Sellis, Tejas Anil Shah, Anna Talas, 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 -- Raido Everest (Estonian)
Mon. 12.15 - 14.00, Narva mnt 18 - 2048 -- Tejas Anil Shah (English)- Mon. 14.15 - 16.00, Narva mnt 18 - 2010 -- Anna Talas (Estonian)
- Tue. 10.15 - 12.00, Narva mnt 18 - 2047 -- Karan Khathuria (English)
- Wed. 14.15 - 16.00, Narva mnt 18 - 1007 -- Henri Sellis (Estonian)
- Wed. 16.15 - 18.00, Narva mnt 18 - 1004 -- Thamara Luup Carvalho (English)
Online studies during COVID-19 outbreak
- As of now, the lectures and practice sessions will take place in hybrid format. The lectures will be held both in-person and streamed online. Practice sessions will be held in-person. The online access will be arranged in Moodle via access to BigBlueButton.
Announcements
- The retake of the final exam will take place on Friday, June 17th, between 12:15-14:15. The exam will be accessible via Moodle in the block corresponding to Week 16. Please make sure that you have a computer with a stable internet connection. The duration of the exam is 2 hours. For additional information about the exam, please refer to the forum of the course in Moodle.
Old announcements
- The final exam will take place on Friday, June 10th, between 12:15-14:15. The exam will be accessible via Moodle in the block corresponding to Week 16. Please make sure that you have a computer with a stable internet connection. The duration of the exam is 2 hours. For additional information about the exam, please refer to the forum of the course in Moodle.
- The retake of the midterm will take place on Friday, June 10th, between 14:45-16:45. The retake exam will be accessible via Moodle in the block corresponding to Week 9. The duration of the retake exam is also 2 hours. For additional information about the exam, please refer to the forum of the course in Moodle.
- The final exam will take place on Friday, May 27th, between 12:15-14:15. The exam will be accessible via Moodle in the block corresponding to Week 16. Please make sure that you have a computer with a stable internet connection. The duration of the exam is 2 hours. For additional information about the exam, please refer to the forum of the course in Moodle.
- The retake of the midterm will take place on Friday, May 27th, between 14:45-16:45. The retake exam will be accessible via Moodle in the block corresponding to Week 9. The duration of the retake exam is also 2 hours. For additional information about the exam, please refer to the forum of the course in Moodle.
- There is no lecture in Theoretical Computer Science on April 15.
- The midterm exam will take place on Friday, April 8th, between 12:15-14:15. It will be held online. The access is via section of Week 9 in Moodle. More information about the exam format was sent via email and published on Moodle forum.
- Unfortunately, we will be permanently canceling the tutorial (practice session) group 2 on Mon. 12.15 - 14.00 taught by Tejas, effective tomorrow, March 7th. The students who attended this group, can now join any other practice session group as follows (no need to change the registration in ÕIS). We appologize for possible incovenience.
- The tutorial, group 5, which is scheduled to take place on March 2nd at 14.15 - 16.00 (taught by Henri), as a matter of exception, will take place ONLINE. The access is via Moodle, Week 3, using the corresponding link.
- The practice sessions on Wednesday, February 23rd, and the lecture on Friday, February 25th, will take place according to the original schedule.
- There will be no tutorials (practice sessions) on February 7-9. The first tutorials will take place on February 14-16. The first lecture will take place on February 11.
Exam dates
- Midterm exam: April 8th at 12:15
- Final exam: May 27th at 12:15
- Midterm exam retake: May 27th at 14:45
- Final exam: June 10th at 12:15
- Midterm exam retake: June 10th at 14:45
- Final exam retake: June 17th at 12:15
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 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
Image credit: Turing Machine, Tom Dunne, American Scientist, March-April 2002