Module Computer Science 2, Computer Science (Bachelor) (ER 8)

English language
Compact font

Color scheme

Module summary

Computer Science 2

INFB210

Prof. Dr. Christian Pape

/

2nd Semester

Informatik 1

none

The students learn about basic algorithms and data structures. They can estimate in which situations specific and complex data types are used, how they work and how much time they take. They are able to prove the correctness of algorithms. In practical assignments the students are enabled to implement various algorithms and data structures.

Written Exam 90 Min. (graded)
Course Computer Science 2

INFB211.a

Lecture

Prof. Dr. Christian Pape

German

5/4

150 hours in total, including 60 hours of contact study.

Module exam

The lecture is divided into several parts building on one another:

  • In the first part, students learn to precisely define algorithmic problems, writing algorithms for in pseudocode, estimating the resource consumption of an algorithm and proving its correctness.
  • Building on this, students learn search and sorting methods, apply the skills acquired in the first part to them and are able to select a suitable method for a problem.They learn the lower bound of this problem and how to prove it.
  • In the third part, they acquire detailed knowledge of the structure and implementation of operations of elementary data structures such as queues, lists and binary trees. The students learn typical application examples for these data structures.
  • The fourth part of the lecture focuses on advanced data structures and the associated algorithms, such as hash tables and binary search trees. They learn how search trees can be balanced.
  • In the final part, the lecture deals with the basics of graphs. The students can apply different representations, such as adjacency matrices and adjacency lists. They learn basic algorithms, such as shortest path search, union find and the calculation of minimum spanning trees to real problems.


  • Lecture notes.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. Third Edition. MIT Press.
  • Robert Sedgewick: Algorithms in Java. Addison Wesley. Third Edition.


Weekly exercises for reviewing lecture content and for exam preparation. Simple tasks in the lecture.

Course Computer Science 2 Laboratory

INFB213

Exercise

Prof. Dr. Christian Pape

German

2/2

60 hours in total, including 30 hours of contact study.

Exercise 1 Semester (not graded)

The students deepen the knowledge acquired in the lecture by implementing and testing selected algorithms in Java. They use standard development environments. The algorithms and data structures to be implemented are used culminating in a final task.

Assignements and basic source code.

Practical exercise with discussion of solutions

Course Theoretical Computer Science 2

INFB212.b

Lecture

Prof. Dr. Heiko Körner

German

3/2

90 hours in total, including 30 hours of contact study.

Module exam

The course deals with the computational limits of modern computer systems, showing the undecidability and intractability of important problems.

Several computational conceps like Turing machines and WHILE-programs are presented. Other topics include the Church-Turing thesis, the theory of NP-completeness and zero-knowledge-proofs.

For this course some basics concerning theoretical computer science are required (regular languages, finite automata, O-calculus, etc.). This knowledge can be purchased in the lecture Theoretical Computer Science I.

  • Discussion at the blackboard
  • Lecture notes
  • Sample solutions for all exercises
  • D. W. Hoffmann: Theoretical Computer Science, 5th edition. Hanser, 2022
  • M. Sipser: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, Inc, 2012

This course will take place as a pure lecture. Numerous exercises deepen selected areas and will be discussed in tutorials.