Topic outline

  • General

    Teaching on the course will mostly return to campus from the beginning of Period IV, viz. 1 March onwards. Only tutorial groups 1 and 2 continue to be conducted online via Zoom. For details, see below.

    A Zulip forum at https://cs-c2160.zulip.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).

    Credits: 5

    Level: Bachelor

    Responsible Professor: Pekka Orponen

    Teaching Period: III - IV (Spring). The course starts on Tuesday 11 January 2022.

    Schedule:

    • Course material reviews ("lectures"): Tuesdays 10:15 - 12:00 T3 (Pekka Orponen)
    • Tutorial sessions (starting Tue 1 March):
      • Tuesdays 16:15 - 18:00 Zoom, channel 663 1382 9636 (Etna Lindy)
      • Wednesdays 10:15 - 12:00 Zoom, channel 663 1382 9636 (Antti Immonen)
      • Wednesdays 12:15 - 14:00 T6 (Siiri Kuoppala)
      • Thursdays 12:15 - 14:00 T6 (Antti Immonen)
      • Fridays 10:15 - 12:00 T6 (Etna Lindy)

     Workload:

    • Lectures: 24h (2h/week)
    • Tutorial sessions in small groups: 24h (2h/week)
    • Independent work: 82h
    • Exam: 3h
    • Total: 133h


    Learning Outcomes: 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 understand how 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.

    Content: 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.

    Study Material: Lecture 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

    Language: English