Fundamental Algorithms

The module provides an overview of fundamental sequential and parallel algorithms, as well as an introduction to the analysis of algorithms. Typical topics include:
Fundamentals: models of computation, complexity measures, loop invariants and induction techniques to prove the correctness of algorithms
Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, median algorithms, lower bounds for sorting, sorting in parallel
Searching: linear and binary search, search trees (AVL Trees), hashing, etc.
Arithmetic problems: parallel prefix computation, parallel matrix and vector operations
Graph algorithms: graph traversal, transitive closure, shortest paths, minimum spanning trees
These algorithms are used as examples to present and exercise the application of models of computation, complexity measures and techniques for analysis and proofs.

Participants understand fundamental algorithms (incl. simple parallel algorithms) and are able to apply them. They can analyze the complexity and the parallelism properties of moderately complex algorithms. For algorithms that are discussed in the module, they are able to prove such properties using the discussed techniques. Participants are also able to assess the appropriateness of these algorithms for specific problems.

IN0001 Einführung in die Informatik 1

This module comprises lectures and accompanying tutorials. The contents of the lectures will be taught by talks and presentations. Students will be encouraged to study literature and to get involved with the topic in depth. In the tutorials, concrete problems will be solved (partially in teamwork) and selected examples will be discussed.

Slides, blackboard

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge, MA, 2001.
- Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, Boston, MA, 2005.
- Russell L. Shackelford , Introduction to Computing and Algorithms. Addison Wesley, 1997.
- Robert Sedgewick, Kevin Wayne. Algorithms. 4th Edition, Pearson Education, 2011.

The examination consists of a written exam of 90 minutes. In the exam, students prove in the given exercises that they have command of the fundamentals of the algorithms and data structures discussed in the module. They are able to apply their knowledge and solve respective algorithmic problems within limited time. Exercise may include:
determining the complexity of sorting, arithmetic or graph algorithms using the discussed complexity models;
determining non-functional properties (correctness, level of parallelism, etc.) of these algorithms;
discussion of the appropriateness of certain algorithms to meet additional requirements.
Answers require own formulations and computations.