Introduction to Theoretical Computer Science
Instructor: Vitaly Skachek
Assistants: Zahra Alijani, Raido Everest, Pilleriin Jukk, Mozhgan Pourmoradnasseri, Rein Prank, Reimo Palm
Language of instruction: lectures are in English, practice sessions are in English/Estonian
Online studies during COVID-19 outbreak
As of now, the lectures and practice sessions will take place in online regime via BigBlueButton. 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, 12:15-13:45.Online practice sessions take place on Mondays, 14:15-15:45 (in English), and on Tuesdays 10:15-11:45 (in Estonian).Online consultations take place on Mondays, 12:15-13:45.
The access to the online classes and consultations is via the corresponding links in Moodle. The videos of lectures and pracice sessions will be recorded.
Announcements
The midterm exam in LTAT.04.001 Introduction to Theoretical Computer Science will take place on Friday, April 16th, between 12:15-14:15. 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 automatically after 2 hours of work.
The exam working environment in Moodle is very similar to that of the homework assignments. In the beginning of the exam you will be asked to declare that you work independently and do not collaborate with anyone else during the exam. The declaration will be available in Moodle from 12:00.
We will open and maintain a helpline in BigBlueButton, which will also be accessible via Moodle. We recommend you to join it, and ask questions if needed.
Old Announcements
- Next Friday, April 2nd, is a Good Friday -- there are no official studies at that day. However, Lecture 8 will take place on April 2nd (Friday) at 12:15-13:45 (regular lecture time) and it will be recorded. You can watch it in the real time via BigBlueButton (BBB). Alternatively, you can watch the recording on April 5 or April 6 in BigBlueButton during the practice session time (the practice sessions will not take place), or at any other time. Vitaly will be available to answer your questions about the lecture in the practice session rooms in BBB during the practice session time slots on April 5th and April 6th (on April 5th till approximately 15:20).
- The practice sessions on February 8, 9 and 10, 2021, are cancelled. The first lecture will take place on February 12 between 12:15-13:45. The information about organization of the study process in the midst of the corona pandemic and the instruction about accessing the online classes will be sent by email.
Exam dates
- Midterm exam: April 16th (12:15-14:15, online, recommended date)
- Midterm exam retake: May 28th and June 11th (14:45-16:45, online)
- Final exam May 28th (12:15-14:15, online)
- Final exam June 11th (12:15-14:15, online)
- Final exam retake: June 18th (12:15-14:15, online, only for those who failed an early attempt)
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