Modulbeschreibung - Detailansicht

Wichtigste Meldungen anzeigenMeldungsfenster schließen
Functional Data Structures
Fakultät für Informatik
Zuordnungen zu SPO-Versionen
Lehrveranstaltungen und Prüfungsveranstaltungen
Allgemeine Daten (Modulhandbuch)
Arbeitsaufwand (Work Load)
Studien- und 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.
Functional programming (IN0003 Introduction to Informatics 2); Discrete mathematics (IN0015 Discrete Structures); Data structures and algorithms (IN0007 Fundamentals of Algorithms and Data Structures)
After the successful completion of this module, students will have an
in-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.
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 and
algorithms 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
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.
Lecture notes, slides, blackboard, online exercises and homework assignments
Chris Okasaki. Purely Functional Data Structures. Cambridge University Press 1999
Tobias Nipkow