Moduldetails
Name Functional Data Structures
Organisation Fakultät für Informatik
Organisationskennung TUINFIN
Anmerkung
ECTS-Credits 5
Gewichtungsfaktor 1
Dauer [nach SPOV] 4
Modul-Kennung IN2347
Versionskurzbezeichnung
Externe Zuordnung
Gültig Von
Gültig Bis
1
2
3
4
5
6
Studienart/Studium
STPV
SPO-Pfad
Empf.
ECTS-Credits
externe Zuordnung
Dauer
GF
Organisation
Organisationskennung
Gültig von
Gültig bis
laufend
1630 14 016, 028 Mathematik, Informatik ( Bachelorstudium)
1630 14 016, 028 Mathematik, Informatik ( Bachelorstudium) 5 4 [SST] 1 Fakultät für Informatik TUINFIN
1630 16 010 Mathematik ( Masterstudium)
1630 16 010 Mathematik ( Masterstudium) 5 4 [nach SPOV] 1 Fakultät für Informatik TUINFIN
1630 16 030 Informatik ( Masterstudium)
1630 16 030 Informatik ( Masterstudium) 5 4 [nach SPOV] 1 Fakultät für Informatik TUINFIN
1630 16 034 Informatik: Games Engineering ( Masterstudium)
1630 16 034 Informatik: Games Engineering ( Masterstudium) 5 4 [nach SPOV] 1 Fakultät für Informatik TUINFIN
1630 16 043 Wirtschaftsinformatik ( Masterstudium)
1630 16 043 Wirtschaftsinformatik ( Masterstudium) 5 4 [nach SPOV] 1 Fakultät für Informatik TUINFIN
1
2
3
4
5
6
Name
Kennung
Empf.
ECTS
Gültig von
Gültig bis
Gewichtungsfaktor
Prüfungsmodus
Anmerkung
Angebotsknoten
KA 1
Prüfungsknoten
IN2347 KA 5 1
Beschreibungen
Export
Export
Allgemeine Daten (Modulhandbuch)
Modulniveau
Kürzel
Untertitel
Moduldauer
Turnus
Sprache
Arbeitsaufwand (Work Load)
Gesamtstunden
Präsenzstunden
Eigenstudiumstunden
Studien- und Prüfungsleistungen
Beschreibung der Studien-/Prüfungsleistungen
The exam takes the form of a written test of 120 minutes or an oral exam of 30 minutes. The exam will assess students’ foundational understanding of functional data structures. This will involve both programming tasks and proofs and will test the students’ ability to use that data structures covered in the lectures and to design new data structures and algorithms based on the methods covered in the module.
Prüfungswiederholung im Folgesemester
Prüfungswiederholung am Semesterende
Beschreibung
(Empfohlene) Voraussetzungen
Functional programming (IN0003 Introduction to Informatics 2); Discrete mathematics (IN0015 Discrete Structures); Data structures and algorithms (IN0007 Fundamentals of Algorithms and Data Structures)
Angestrebte Lernergebnisse
After the successful completion of this module, students will have anin-depth understanding of a range of functional data structures and are able to prove properties about them with the help of a computer-based proof assistant. Students will be able to- select suitable implementations of functional data structures for common programming tasks,- design and implement new functional data structures that are based on the principles covered in the module,- prove the correctness and complexity of the data structures on paper and with the help of a proof assistant.
Inhalt
The module introduces students to the design and analysis of data structures for functional programming languages. It assumes that the students are familiar with functional programming and with running time analysis of algorithms. The module covers a range of functional data structures with an emphasis on their precise analysis. Proofs of both functional correctness and complexity will be a core part of the module Proofs are carried out with the help of a computer-based proof assistant. An introduction to the proof assistant is part of the module.A selection of the following non-exhaustive list of data structures andalgorithms will be covered:- Sorting- Search trees: Unbalanced trees, AVL trees, Red-Black trees, 2-3 trees, Weight balanced trees, Splay trees, Tries- Other trees: Quad trees, Finger trees- Huffman coding- Priority queues: Braun trees, Leftist heaps, Skew binomial heaps, Skew heaps, Pairing heaps, Fibonacci heaps- Dijkstra's algorithm- String matching
Lehr- und Lernmethode
The module consists of lectures and tutorials. In the lectures, the material is presented by the teacher, in dialogue with the students. During the tutorials, the students work on given exercises either individually or in small groups with help from the tutors. Exercises can be computer-based as well as paper and pencil based.
Medienformen
Lecture notes, slides, blackboard, online exercises and homework assignments
Literatur
Chris Okasaki. Purely Functional Data Structures. Cambridge University Press 1999
Modulverantwortliche*r
