Module Computer Science 2, Media Computer Science (Bachelor) (ER 5)

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