Service and Software Engineering

Interim Professor: Dr. Thomas Göthel

Ankündigung der Lehrveranstaltung / Course Outline

Foundations of Computer Science im WS 2014 / 2015

Lecturer: PD Dr. Henning Bordihn
Program Master Cognitive Systems
SWS: 2
Credits: 6
Zuordung/Module: FM2


Form Day Time Room Start Lecturer
Consultation Thu 18:15-19:45 16.10. Henning Bordihn


This is a reading course. Video lectures provided in the internet can be used in addition. Details are given in the slides of the Introduction (see below).

The course covers two fundamental topics:

1. Theory of Computation

  • Finite State Automata
  • Determinism versus Nondeterminism
  • Regular Expressions
  • Context-Free Grammars
  • Pushdown Automata
  • Turing Machines and Undecidability

  • 2. Fundamentals of Computing

  • Algorithms and their Complexity; Growth of Functions
  • NP-Completeness
  • Fast Algorithms (Paradigms, Searching, Sorting)
  • Recursion

  • Slides and Assignments:

    0 Introduction fm2_welcome.pdf (491 KB)
    1 Assignment 1: Finite Automata assignment_1.pdf (75 KB)
    2 Assignment 2: Regular Expressions assignment_2.pdf (72 KB)
    3 Assignment 3: Context-Free Languages assignment_3.pdf (77 KB)
    4 Assignment 4: Pushdown and Turing machines assignment_4.pdf (78 KB)
    5 Assignment 5: Turing machines, Deciding Languages, Running Time assignment_5.pdf (83 KB)
    6 New Text: P and NP, NP-complete problems, Reductions fundamentals_1.pdf (256 KB)
    Assignment 6: NP-complete problems, Reductions assignment_6.pdf (94 KB)
    7 Video Lectures Algorithmic Thinking fundamentals_2.pdf (311 KB)
    Assignment 7: Growth of Functions, Devide and Conquer, Dynamic Programming assignment_7.pdf (84 KB)


    Oral examination (20 minutes), individual.


    J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Pearson, 2013, ISBN 1292039051.

    R. Sedgewick, K. Wayne: Algorithms. Addison-Wesley, 2011, ISBN 032157351X.