Programming Algorithms

Understand and implement basic algorithms for recurring tasks and evaluate an algorithm’s runtime and correctness based on common standard criteria.

In addition to competence in using a programming language, one needs an understanding of basic procedures and of the data representations used with them. These are the algorithms and data structures to be expressed in a programming language.

For recurring tasks, there are proven standard solutions that you should know, and you should be able to explain how they work. For example, algorithms on graphs can be applied to many tasks that can be formulated using this mathematical model.

Methodological tools like (loop) invariants help to understand and to reason about algorithms as well as to systematically develop algorithms.

When processing large amounts of data, it is especially important to consider how the runtime of algorithms and their memory requirements develop as the amount of data grows. This growth can be captured with the O-notation, denoting the asymptotic complexity.

The students

• understand and apply the concepts of basic algorithms and data structures such as search algorithms, hash tables, and algorithms on graphs (e.g., topological sorting, depth and breadth-first search).
• can understand existing programs of other programmers and explain how they work by recognizing standard solutions in them.
• can program basic algorithms themselves and adapt them to task variants.
• can use recursion in the design of algorithms as required and program it.

The students

• understand the concept of "asymptotic complexity" and know the relevant properties of important complexity classes.
• use asymptotic complexity classification to evaluate resource requirements (runtime and memory) of algorithms and to compare them.
• know lower bounds for runtime and memory requirements of basic procedures or tasks.
• can select suitable algorithms from libraries on the basis of task-related parameters and trade-offs and justify their decision.

The students

• can reason about the correctness of programs as well as precondition to be met for correct results (e.g., by using loop invariants).
• can be guided by correctness considerations when constructing their own algorithms and programs.