CS-C2150 Theoretical Computer Science, Spring 2019
Compulsory course of the Computer Science and Engineering major.
Credits: 5
Level: Bachelor
Teacher: Prof. Pekka Orponen (professor responsible for the course)
Teaching Period: III - IV (Spring). The Course starts on Tuesday 08.01.2019, 10:15 - 12:00, T1 / C202 Tietotekniikka
Schedule:
- Lectures: Tuesdays 10:15 - 12:00
- Exercise sessions (starting Jan 14, 2019):
- Mondays 14:15 - 16:00 TU5 / 1194 TUAS Maarintie 8
- Tuesdays 16:15 - 18:00 T6 / A136 Tietotekniikka
- Wednesdays 10:15 - 12:00 T6 / A136 Tietotekniikka
- Thursdays 12:15 - 14:00 T6 / A136 Tietotekniikka
- Fridays 10:15 - 12:00 T5 / A133 Tietotekniikka
Workload:
- Lectures: 24h (2 hour lectures, once a week)
- Exercises in small groups
- Independent work
- Exam: 3h
Learning Outcomes:
Theoretical computer science comprises the science of computation, and
the science of software. Science is knowledge that helps us make
predictions. The stronger the science, the stronger the predictions. The
science of computation tells us what is computation, what are the
different types of computing machines, and what are their computing
powers. Using this science, we can predict (indeed, prove!) that some
computational problems are easy, some are hard, and some are impossible
to solve! The science of software allows us to make predictions about
the programs that we write: will my program always terminate? might it
crash? will it always produce the right result? etc. In this course you
will learn the basic models of computation (finite automata, regular
expressions, context-free grammars, Turing machines). You will solve a
set of computerized assignments where you will build such computing
machines and answer fun questions about them.
Content:
Finite automata and regular languages. Context-free grammars and
pushdown automata. Turing machines and computability.
Assessment Methods and Criteria: Exam, computerized assignments, and home assignments
Study Material: Lecture notes and slides; Textbook (recommended but not obligatory) Michael Sipser, Introduction to the Theory of Computation; and other separately announced study material
Substitutes for Courses: 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
Lecturer: Prof. Pekka Orponen