Introduction to Theoretical Computer Science
Instructor: Vitaly Skachek
Assistants: Eldho Thomas, Ivo Kubjas, Mozhgan Pourmoradnasseri, Ülo Reimaa, Rein Prank, Reimo Palm
Lecture: Monday 12:15 - 14:00, J. Liivi 2-111
Practice sesssions:
Tuesday 08:15 - 10:00, J. Liivi 2-202 and/or J. Liivi 2-206 -- Eldho (in English)
Tuesday 14:15 - 16:00, J. Liivi 2-207 -- Ivo (in Estonian)
Wednesday 08:15 - 10:00, J. Liivi 2-405 -- Mozhgan (in English)
Wednesday 14:15 - 16:00, J. Liivi 2-207 -- Mozhgan (in English)
Wednesday 16:15 - 18:00, J. Liivi 2-405 -- Ülo (in Estonian) Note: two groups of practice sessions on Tuesday 08:15-10:00 will be joined together, and the joint practice session class will take place in J. Liivi 2-202.
Office hours:
- Vitaly Skachek: Monday 16:00-17:00, Ülikooli 17-224 (Paabel)
- Eldho Thomas: Wednesday 14:00-15:00, Ülikooli 17-225
- Ivo Kubjas: Monday 16:00-17:00, Ülikooli 17-225
- Mozhgan Pourmoradnasseri: Tuesdays 15:00-16:00, Ülikooli 17-327
- Ülo Reimaa: Wednesday 14:00-15:00, Ülikooli 17-225
- Reimo Palm: contact by email
Language of instruction: lectures are in English, practice sessions are in English/Estonian
Retake of the final exam
The retake of the final exam will take place on Monday, June 17th, at 14:15. Room: J. Liivi 2-403. The duration is 2 hours. Any printed and hand-written materials can be used in the exam. No electronic devices are allowed.
You are eligible to retake the final exam if you received grade F in the course (after taking either exam on June 4, on June 10, or if you did not take any final exam). If you passed the course, you still can ask to get the grade F in the first attempt and to retake the final exam. In that case please contact Vitaly as soon as possible.
Final exam
- The final exam will take place on June 4 and June 10 (students choose one of the two dates). The exam will start at 14:15(on each of the two days) and will last for 2 hours. Any printed and hand-written materials can be used in the exam. On the other hand, no electronic devices are allowed.
The exam on June 4 will take place in rooms Liivi 2-111, -511 and -512. The exam on June 10 will take place in rooms Liivi 2-111 and -224.
- The retake of the midterm exam will take place after the main exam and a short break, on each of the dates June 4 and June 10, starting at 16:35. It will last for 1 hour and 40 minutes. You can re-take the midterm if you want to improve your grade, but in that case the latest grade will be taken into account, even if it is lower.
Schedule update
Since there are no studies in the university on May 1st, the practice sessions on Tuesday, April 30th, and Wednesday, May 1st, are cancelled. The lecture on Monday, April 29th, will take place as usual.
Announcements
The midterm exams have been graded now. The grades are now visible in Moodle. You can view your checked paper copy of the exam in Vitaly's office, Paabel 224.
Midterm exam
The midterm exam will take place on Monday, April 15, at the lecture time (12:15-13:55). The duration of the exam is 1 hour 40 minutes. In addition to the regular lecture hall Liivi 2-111, we will also use room Liivi 2-206. The students whose family name starts with A-P will sit the exam in room 111, and the students whose family name starts with R-Z will sit the exam in room 206.
The exam is an "open-book". Any printed and hand-written materials (books, notes, print-outs) can be used. No electronic devices (not even calculators or electronic watches) are allowed in the exam.
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