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.
The lecture is divided into several parts building on one another:
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.
This course will take place as a pure lecture. Numerous exercises deepen selected areas and will be discussed in tutorials.