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
Updated information about the final exams and retakes of the exams:
- The retake of the final exam will be on June 19th at 12:15-14:15. The exam will be held online using Moodle. This retake is generally indended for the students who failed the final exam or the course. If you opt for the retake, then the latest grade will be taken into account.
The examples of previous year midterms and finals (partly with solutions) are available here.
https://courses.cs.ut.ee/2020/IntroTCS/spring/Main/Links
Old announcements
- There are two final exam dates: Friday May 29th and Friday June 12th, both at 12:15-14:15. The duration of each exam is two hours. Both exams will be held online using Moodle (if there will be no major change in the university policy). You can choose one of the two dates. Please register to the selected exam date in ÕIS if you did not do so yet.
- The retake of the midterm exam will be on the same dates as the final exam: May 29th and June 12th, at 15:15-17:15 (the duration is two hours). The retake exams will also be held online, in a format similar to the original midterm exam. Generally, you can opt for a retake if you are not saitsfied with your results in the original midterm exam, but please bear in mind that the latest grade will be taken into account.
- An additional consultation (for the final exam) will take place on Thursday, May 28th, at 10:15-11:45, via BigBlueButton (access via Moodle link). You are welcome to bring your own questions.
- There is a holiday on May 1st. Unfortunately, since we missed a few lectures due to the schedule constraints, the lecture in LTAT.04.001 Introduction to Theoretical Computer Science on Friday, May 1st, will take place as usual, at 12:15. It will be recorded in BigBlueButton, so if you cannot attend and missed it, you can watch it later.
- On Monday, April 20th, between 10:15-11:45 we have a Lecture instead of a Practice Session. The access to the lecture is via Moodle as usual. The topic is introduction to Turing machines. On Friday, April 24th, 12:15-13:45, we will also have a Lecture, according to the usual schedule.
- The online midterm exam will take place on Friday, April 17th, during the lecture time 12:15-14:15. The exam will cover the topics of the first eight weeks of the semester (up to and including the pumping lemma).
- The exam will be accessible via Moodle. Please make sure that you have a computer with a stable internet connection. The duration of the exam is 2 hours. The exam will open at 12:15. The ability to edit the answers will be interrupted after 2 hours of work.
- We will open and maintain a helpline in BigBlueButton, which will also be accessible from Moodle.
- Due to the Good Friday holiday, there is no lecture on Friday, April 9th.
- There will be a practice session on Monday, April 13th, which will cover the topic of the pumping lemma.
- There will be an additional online consultation on Wednesday, April 15th, between 16:15-17:45. We will answer your questions if any.
- You can see examples of previous midterm exams here: https://courses.cs.ut.ee/2020/IntroTCS/spring/Main/Links . However, we will change the format somewhat due to the online nature of the exam.
- 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.
- 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 (updated)
- Midterm exam: April 17, 12:15-14:15 (lecture time, online)
- Midterm exam retake 1: May 29, 15:15-17:15 (online)
- Midterm exam retake 2: June 12, 15:15-17:15 (online)
- Final exam (first date): May 29, 12:15-14:15 (lecture time, online)
- Final exam (second date): June 12, 12:15-14:15 (lecture time, online)
- Final exam retake: June 19, 12:15-14:15 (lecture time, online)
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