Because of the coronavirus situation, all teaching on the course takes place online on the Aalto Zoom channel 663 1382 9636. Note that you must be signed in to Zoom with your Aalto e-mail address in order to participate.
In addition, a Zulip forum at https://cs-c2160.zulip.cs.aalto.fi is available for general discussion and collaboration on the course topics.
Compulsory course of the Computer Science and Data Science majors (BSc level).
Responsible Professor: Pekka Orponen
Teaching Period: III - IV (Spring). The course starts on Tuesday 12 January 2021.
Schedule (all teaching online):
- Lectures: Tuesdays 10:15 - 12:00 (Pekka Orponen)
- Tutorial sessions (starting Tue 12 Jan):
- Tuesdays 16:15 - 18:00 (Sander Aarts)
- Wednesdays 10:15 - 12:00 (Trang Nguyen)
- Wednesdays 12:15 - 14:00 (Trang Nguyen)
- Thursdays 12:15 - 14:00 (Sander Aarts)
- Fridays 10:15 - 12:00 (Siiri Kuoppala)
- Lectures: 24h (2h/week)
- Tutorial sessions in small groups: 24h (2h/week)
- Independent work: 82h
- Exam: 3h
- Total: 133h
After the course you know the most important mathematical models of
computation and their characteristics. You can model
computation using finite automata and describe simple syntactic patterns
with regular expressions and context-free grammars. You understand the
possibilities and limitations of the computation models and description
formalisms studied during the course, and know their relationships. You
the Turing machine model characterises everything that can be computed
with a computer program, and that there are well-defined problems that
cannot be solved by any program.
Finite automata and regular languages. Context-free grammars and
pushdown automata. Turing machines and computability.
Assessment Methods and Criteria: Exam, tutorial problems and computerised assignments.
notes/slides and other separately
announced study material. Supporting textbook (recommended but not obligatory): Michael
Sipser, Introduction to the Theory of Computation, 3rd Ed. (2013).
Substitutes for Courses: CS-C2150 Theoretical Computer Science, ICS-C2000 Theoretical Computer Science, T-79.1001 Introduction to Theoretical Computer Science T (4 cr), T-79.1002 Introduction to Theoretical Computer Science Y (2 cr).
Prerequisites: CS-A1110 / CSE-A1110 Programming 1 and CS-A1120 / ICS-A1120 Programming 2 or CS-A1111 / CSE-A1111 Basic Course in Programming Y1 and CS-A1121 / CSE-A1121 Basic Course in Programming Y2, MS-A0401/A0402/A0409 Foundations of discrete mathematics.
Grading Scale: 0-5