Official Course Description
This module introduces the mathematical theory of computation. Several types of abstract computational machines (called automata) are introduced together with the associated theory of formal languages. A formal language is a set of words over a defined alphabet that are well-formed according to a specific set of rules, called the grammar of the language. After studying the relationship between automata models and classes of formal languages, this course addresses the fundamental question “What problems can a computer possibly solve?” by characterizing those solvable problems, equivalently, through Turing machines, random access machines, recursive functions and lambda calculus. A full answer to the related question, “How much computational resources are needed for solving a given problem?” is not known today. However, the basic outlines of today’s theory of computational complexity will be presented up to the most famous open problem in computer science, namely the “P = NP” question: if a computer could guess the right answer to a computational problem (and only needs to check its correctness), would that computer be faster than another one that cannot guess the right solution? This may seem a ridiculously obvious case of a clear YES answer, but in fact it is considered by many to be the deepest open question in contemporary mathematics (and computer science, of course).
This module provides the core education in theoretical computer science. The material covered in this module gives students access to any field in computer science, which is based on discrete-mathematical formal foundations, such as the theory of automata and formal languages or compiler design.
Course literature
- Michael Sipser: Introduction to the Theory of Computation,2nd edition, PWS Publishing Company, 1997. (Primary Literature).
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman: Introduction toAutomata Theory, Languages, And Computation, 3rd edition, Pearson, 2006.
Grading and final exam
The grades for this lecture will be determined by a final written exam (100%). If not otherwise indicated, it will cover all content of the course.
Bonus Achievements
The grade of the final exam can be improved by 0.33 grade points if the following two conditions are both fulfilled:
- at least 50% of the points from the weekly quizzes of the live lecture are achieved, and
- at least 50% of the points from the weekly homework assignments are achieved.
There is no re-scheduling, repetition or compensation option for the Bonus Achievements in case of illness. This holds even if a sick certificate is presented.
Course communication
All official announcements for this course will be posted via the below announcement forum, to for which all students have a mandatory subscription. Additionally, there is a forum for interaction with the instructor and the TA wrt. general questions. All course-related (non-private) communication should be placed to that general discussion forum.
Announcements
Course related questions and inquiries
Culture of interaction
- Please feel free to ask questions at any time!
- Please tell the instructor, if he is too slow / fast / boring / excited / . . . by giving feedback via the lecture forum or in a private communication.
- Please use the “virtual” open-door policy, i.e. send a brief message and we can have a meeting.
Course Setup
Officially, this course has two lecture slots per week, namely Mondays, 14:15-15:30, Tuesdays, 17:15-18:30 and Thursdays 17:15-18:30. The initial (online!) meeting of the course will take place on Monday, February 1, 14:15-15:30 in this time period. You can access the meeting via the link further down this page.
Afterwards, however, we will chose a more flexible blended learning approach. Specifically, the course is taught in a partially synchronous (i.e. live), partially asynchronous, and partially personal way. What this exactly means is discussed below.
Lecture notes – “Delivery” of factual content
During the semester, the instructor will newly develop lecture notes, i.e. pretty much a book on machine learning with examples and explanations. It will be a typesetted document that will finally contain all lecture contents that are required to be known to pass the exam. Every week, students are required to read a new section of these lecture notes. Thereby they will passively acquire the theoretical knowledge of the lecture. Certainly, acquiring knowledge just by reading is a tedious task. Therefore, this “core content delivery” is enriched by several additional offers.
Forum to collect typos / mistakes
Live lecture – Reminding, strengthening, exploring
Within the Monday lecture slot, more precisely on Mondays, 14:15-15:30 using the link below, a live (for now) online meeting (on Zoom) takes place. During that meeting, a “camera on” policy holds, i.e. all students are supposed to switch on their cameras. In addition, the Thursday lecture slots, more precisely Thursdays, 17:15-18:15, will give room for more global in-class Q&A. No additional “content” will be discussed on Thursdays and the instructor will leave as soon as no further questions are in the room.
The Monday meetings will have the following components:
- Quiz: All meetings will start by a Moodle quiz for which the students have 10 minutes of time to complete it. The quiz is an open-book quiz, i.e. students are allowed to use the lecture notes or whatever other information source that could help them to solve the quiz. The quiz is also one of the two mandatory components of the Bonus Achievements.
- Strengthening & Exploring: After the quiz, depending on the content, additional examples, re-iteration of theory, proof development practicing, quick paper and pencil tasks etc. are offered by the instructor (partially to be done in groups) in order to dive deeper into the topic.
- Q & A: Finally, students will have the opportunity to ask questions. Plenty of time, will be available for this part, if students desire it.
The Thursday meetings will have the following component:
- Q & A: Students will have the opportunity to ask questions. Plenty of time, will be available for this part, if students desire it.
“Bookable” slot – Personalized content support
During the the Tuesday slot, i.e. on Tuesdays 17:15-18:30, a single student or a group of students can “book” slots of 10 minutes (maximum 2 slots, if in groups) with the instructor for a more personalized support with the lecture content. With this offer, the instructor wants to overcome the issue of sometimes strongly varying learning habits of students, which is in particular pronounced in large groups. Use the below scheduling tool to book a slot and the below zoom link to enter the meeting.
Scheduler for “bookable slots”
Bookable slots meeting (online)
Homework assignments
Per week, four tasks are published as homework assignments on Moodle. They will support the student in further practicing the content that was read and discussed in the previous week. Also, they are the second component of the Bonus Achievements.
- Submission
- deadline: weekly on Mondays, 12:00 PM
- format: PDF only, via Moodle, at the bottom of this page
- in groups: 1-3 students, depending on class size, participation, etc. (we might have to adapt this depending on the number of submissions)
- Groups are defined via the Submission group assignments Database activity below. Follow the instructions given with the activity.
- Only one person per group submits the homework. All other will get the points assigned.
- Evaluation
- exercises evaluated with points by TAs
- at least 50% of the points are need as one of the requirements of the Bonus Achievements
- Reference solutions
- TAs provide graded homeworks and tutorials discuss solutions.
- Reference solutions will be published one week after the content has been discussed in the tutorials.
- Cheating
- no points are given for copied homework (affects both parties)
Forum to find submission partner
Tutorials
Once per week, a TA offers a tutorial. In the tutorial, students can ask further questions. Moreover, the TAs discuss the solutions to the previous assignments and answer questions on the new assignments. The tutorial takes place on Wednesdays, 15:45-17:00 in an online format.