You are here: Home › Teaching › Summer Term 2014 › Computer Science Theory (Bridging …

Computer Science Theory (Bridging Course) (Tutorial)

The course introduces the foundations of theoretical computer science. The first part covers automata theory and formal languages and grammars. The second part provides a precise definition of the term "computability" and shows the limitations of computational models. The third part introduces complexity theory, especially the class of NP-complete problems.
Course type Tutorial
Instructors Prof. Dr. Andreas Podelski, Matthias Heizmann, Christian Schilling
Tutorial individually
First session Tue 29th April 2014, 12:00, building 101, room 00 010/014
Language of instruction English
Exam 12th August 2014, 11:00, building 101, room 00 010/014
Course Catalog Computer Science Theory

 

News

  • July 29th: There will be a two-hour meeting where we answer your questions on Friday, August 8th, 14:00-16:00, building 101 room 02-016/18.
  • July 22nd: Details about the final exam were updated (topics: everything including the topics of the intermediate exam).
  • July 8th:
    • We change the course interval back to one-week.
    • The last exercise of the intermediate exam is considered a bonus exercise.
  • June 15th: The time for the intermediate exam was corrected (12:15).
  • June 3rd: A mistake in the second lecture notes, chapter Closure Properties, was fixed.
  • May 30th: The intermediate exam was added to the exam section. Please note the different room.
  • May 19th:
    • Starting on May 26th, we will change the course interval from one-week to two-week. This means that tutorials are only visited every second week, but for 60 minutes instead of 30 minutes. Accordingly, exercise sheets will be designed for two weeks of work. However, lectures are still given weekly.
    • The hint in exercise 3 on sheet 3 was misleading. It was removed.
  • May 15th: The section "Lectures" was added.
  • May 9th:
    • The lecture script was updated (this will only be announced in the "Script" section below in the future).
    • A typo was corrected on exercise sheet 1.
  • April 30th:
    • The introduction slides were updated. They now contain a page with all relevant email addresses. These were also added below.
    • A test file and an exercise sheet solution template for TeX was added.
  • April 29th:
    • The section "Formalities" was updated according to the introductory presentation. The slides can be found below.
    • A short introduction to TeX was added.
  • April 10th: The course script has been relocated on our web server. The link below was updated accordingly.

Formalities

There will be no classical lecture. Instead, the participants are supposed to work through the course script (see below) themselves. We provide exercise sheets and tutorials every week to make sure the contents were understood correctly.

Admission criterion

Each exercise sheet will contain several exercises.

We have two criteria for exam admission.

  1. All tutorials are attended.
  2. All exercises are solved.

In case a tutorial cannot be attended (illness etc.), the tutors must be informed in advance. To contact the tutors, use this email address: csBridgeTutors@david-zschocke.de

Exercises & Tutorials

Every week we publish a new exercise sheet and offer an individual tutorial for each participant of half an hour. The participants have to weekly perform the following algorithm.

  1. Register for a tutorial [link removed].
  2. Hand in the solution (typeset in TeX) just until the tutorial to this email address: csBridgeSolutions@david-zschocke.de
  3. Visit the tutorial duly and bring a printed version of the solution.
  4. Present the solution in the tutorial.

We appreciate discussion of the exercise sheets in groups. However, solutions have to be written individually.

Exam

There will be a written exam on Tuesday, the 12th of August 2014, at 11:00 in building 101, room 00 010/014.

The final exam will cover all material we have seen in the exercises, including those already covered in the intermediate exam.

We have an intermediate exam. We grant points which count for the final exam.

  • The intermediate exam covers the contents of the lecture including chapter 1 (basic definitions, especially formal languages) and chapter 2 (finite automata and regular languages).
  • The intermediate exam takes place on June 17th (Tuesday) at the beginning of the lecture (12:15). We change the location to building 101, room SR 00-010/14.

Lectures

Lectures cover the following topics:

  • We discuss how to solve the exercises in order to succeed in the final exam.
  • We clarify common mistakes from the tutorials.
  • We answer questions. Please send them to Christian in advance.

 

Lectures will take place irregularly both on Tuesday and Wednesday from 12 PM to 14 PM (c.t.) in building 051, room SR 00-031. The dates will be announced below.

Resources

Script

You can find the course script here. The login and password will be provided at the beginning of the lecture period.

changes: (Note: Typos do not change the meaning of the contents; else we make this clear.)

  • May 9th: added table of contents; corrected typos in Chapter 1
  • May 19th: corrected typos in Chapter 2.1
  • May 26th: corrected typos in Chapter 1 and 2.1
  • June 4th: corrected typos in Chapter 2 and 3
  • June 24th: corrected typos in Chapter 3 and 4.1
  • July 8th: corrected typos in Chapter 4 and 5
  • July 15th: corrected typos in Chapter 5
  • July 18th: corrected typos in Chapter 6
  • July 22nd: corrected typos in Chapter 6

Exercises

Presentations

TeX / LaTeX

To typeset documents in TeX, a distribution is needed. There are many packages for different applications. Altogether, they require much disk space. Usually a thin version with just the most important packages is enough. Packages can be installed separately if needed. Here are the three most prominent distributions (cf. Wikipedia "Distributions").

A PDF file can be created by the command pdflatex. Many people prefer a TeX specific editor where no shell command is needed. Some of them are listed below (cf. Wikipedia "TeX editors").

There are many tutorials to learn the basics of TeX available on the web.

For testing the system, the following test file can be used. It needs no further packages.

The tutors provide the following template for the solutions. The files have to be in the same folder. Only the TeX file needs to be edited.

Literature

    • H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2nd edition , 1997, 361 pages, Prentice Hall, New Jersey. ISBN 0-13-262478-8
    • J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd edition 2006, 750 pages, Prentice Hall, New Jersey . ISBN 0-32-145536-3