Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Course INF-02-06-K-2

Algorithms and Data Structures (4V+2U, 8.0 LP)

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
CP, Effort 8.0 CP = 240 h
Position of the semester 1 Sem. in SuSe
Level [2] Bachelor (Fundamentals)
Language [DE] German
Lecturers
Area of study [INF-PFL] Mandatory Modules
Livecycle-State [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.

Requirements for attendance (informal)

Courses

Requirements for attendance (formal)

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