## Module Handbook

• Dynamischer Default-Fachbereich geändert auf INF

# Course INF-02-06-K-2

## Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 8.0 CP 156 h
4 V Lecture 56 h
2 U Exercise class (in small groups) 28 h
(4V+2U) 8.0 CP 84 h 156 h

## Basedata

SWS 4V+2U 8.0 CP = 240 h 1 Sem. in SuSe [2] Bachelor (Fundamentals) [DE] German Schweitzer, Pascal, Prof. Dr. (PROF | DEPT: INF) [INF-PFL] Mandatory Modules [NORM] Active

## Possible Study achievement

• Verification of study performance: proof of successful participation in the exercise classes (ungraded)
• Details of the examination (type, duration, criteria) will be announced at the beginning of the course.

## Contents

• Characteristics and properties of algorithms (computability, correctness, pseudocode notation)
• Runtime of algorithms (runtime and efficiency, growth of functions, asymptotic notation and calculation rules, recursive algorithms, amortized analysis)
• Runtime of operations of elementary data structures
• Sorting algorithms (primitive sorting algorithms, quicksort, mergesort, heapsort, external sorting, sorting without comparisons)
• Data structures for dictionaries (binary search trees, balanced search trees, B-trees, hashing)
• Graphs and important graph algorithms (data structures for graphs, traversing, shortest paths, minimum span trees)
• Basic Design Methods (Divide-and-Conquer, Dynamic Programming, Greedy Algorithms, Backtracking)
• Basic concepts of complexity theory (Turing machines, classes P and NP, Karp reduction, some important NP-complete problems)

## Literature

• Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. Oldenbourg Verlag, 2013.
• Mehlhorn, Kurt, and Peter Sanders. Algorithms and data structures: The basic toolbox. Springer Science & Business Media, 2008.
• Nebel: Entwurf und Analyse von Algorithmen. Springer-Verlag, 2012.
• Ottmann, Widmayer: Algorithmen und Datenstrukturen. Springer-Verlag, 2012.

None

## References to Course [INF-02-06-K-2]

Module Name Context
[INF-02-06-M-2] Algorithms and Data Structures P: Obligatory 4V+2U, 8.0 LP
[INF-02-41-M-2] Programming 2 P: Obligatory 4V+2U, 8.0 LP
[INF-82-54ITI-M-2] Algorithms and Data Structures P: Obligatory 4V+2U, 8.0 LP
[INF-82-54-M-2] Algorithms and Data Structures P: Obligatory 4V+2U, 8.0 LP
[MAT-INF-10-M-3] Computer Science for Mathematicians P: Obligatory 4V+2U, 8.0 LP