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

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.

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

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.