University of Freiburg | Faculty of Applied Sciences | Institute for Computer Science | Computer Networks and Telematics
The tele Research Group
Home         Teaching         Research        Tools         Openings        Publications





Applied Computer Science II 
PD Dr. Richard Mayr

Winter Term 2003/2004

Organizational Notes

  • Lectures: Tuesdays 9:00-11:00 ct, Thursdays 9:00-10:00 ct, Room 00-010/14, building 101.
  • Tutorial: Thursdays, 10:00-11:00.
  • The course will be taught in English, and all course materials and tutorials will be offered in English as well. The course is intended for international students in the Master of Science in Applied Computer Science programme.
  • Information will constantly be added to this web site, so check back regularly.

Course Description

This course will address theoretical aspects of computer science. It comprises the fundamental mathematical properties of computer hard and software. We will see what can be computed, and what cannot, and if it can be computed, how hard (efficient) it is to compute it. More specifically, we will study automata, languages, grammars, turing machines, decidability, complexity theory and logic. The course is entirely in English!


Course Structure and Materials

(Most slides taken over from ACS II in 2002, with kind permission from Luc de Raedt.)

  1. Organization
  2. Motivation
  3. Logic
  4. Predicate Calculus
  5. Resolution in FOL (Powerpoint format), PDF Format PDF BW 4 on 1
  6. Regular languages. Powerpoint PDF (Color) PDF (BW) Postscript Postscript (4 on 1)
  7. Grammars. Powerpoint PDF (2 on 1) PDF (4 on 1)
  8. Context-free languages and pushdown automata. Powerpoint PDF (2 on 1) PDF (4 on 1)
  9. Turing Machines. Powerpoint PDF (1 on 1) PDF (2 on 1) PDF (4 on 1)
  10. Decidability. Powerpoint PDF (1 on 1) PDF (2 on 1) PDF (4 on 1)
  11. Reductions. Powerpoint PDF (1 on 1) PDF (2 on 1) PDF (4 on 1)
  12. Time Complexity. Powerpoint PDF (1 on 1) PDF (2 on 1)
  13. Space Complexity. Powerpoint PDF (1 on 1) PDF (2 on 1)


Thursdays, 10:15-11:00, room 00-010/14, building 101.


  1. Michael Sipser. "Introduction to the theory of computation". PWS Publishing Co., Boston, MA, 1996.

  2. J. D. Ullman, J. E. Hopcroft, R. Motwani. "Introduction to Automata Theory, Languages, and Computation". Addison Wesley, second edition, 2001.