Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-02-06-M-2

Algorithms and Data Structures (M, 8.0 LP)

Module Identification

Module Number Module Name CP (Effort)
INF-02-06-M-2 Algorithms and Data Structures 8.0 CP (240 h)

Basedata

CP, Effort 8.0 CP = 240 h
Position of the semester 1 Sem. in SuSe
Level [2] Bachelor (Fundamentals)
Language [DE] German
Module Manager
Lecturers
Area of study [INF-PFL] Mandatory Modules
Reference course of study [INF-82.79-SG] B.Sc. Computer Science
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U INF-02-06-K-2
Algorithms and Data Structures
P 84 h 156 h
U-Schein
ja PL1 8.0 SuSe
  • About [INF-02-06-K-2]: Title: "Algorithms and Data Structures"; Presence-Time: 84 h; Self-Study: 156 h
  • About [INF-02-06-K-2]: The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.
    • It is a prerequisite for the examination for PL1.

Examination achievement PL1

  • Form of examination: written exam (Klausur) (120-150 Min.)
  • Examination Frequency: each semester
  • Examination number: 60206 ("Algorithms and Data Structures")

Evaluation of grades

The grade of the module examination is also the module grade.


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)

Competencies / intended learning achievements

The students know basic algorithms and data structures (search methods, sorting methods, balanced search trees, hashing) and are able to,
  • describe algorithms using basic data structures and algorithmic approaches,
  • use standard methods for determining and describing the runtime of algorithms,
  • apply common techniques for the design of algorithms to new problems,
  • prove for simple problems that no efficient algorithm can exist,
  • classify and compare problems according to their runtime complexity and structure.

In the exercises they have worked out a safe, precise and independent handling of the terms, statements and methods from the lecture.

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 of the module (informal)

Modules:

Requirements for attendance of the module (formal)

None

References to Module / Module Number [INF-02-06-M-2]

Course of Study Section Choice/Obligation
[INF-82.79-SG] B.Sc. Computer Science [Compulsory Modules] Software Development [P] Compulsory
[WIW-82.176-SG#2009] B.Sc. Business Administration and Engineering specialising in Computer Science (2009) [2009] [Fundamentals] Field of study: Computer Science [P] Compulsory
[WIW-82.?-SG#2021] B.Sc. Business Administration and Engineering specialising in Computer Science (2021) [2021] [Specialisation] Field of Study: Computer Science [P] Compulsory
Module-Pool Name
[MV-MB-INF-2022-MPOOL-6] Wahlpflichtmodule M.Sc. Maschinenbau mit angewandter Informatik 2022
[MV-MBINFO-MPOOL-6] Wahlpflichtmodule Maschinenbau mit angewandter Informatik