| Allgemeine Angaben |
|
| Functional Data Structures (IN2347) | | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
| Angaben zur Abhaltung |
|
See also http://www21.in.tum.de/teaching/FDS/
The course 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 course 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 course. Proofs are carried out with the help of the computer-based proof assistant Isabelle. An introduction to Isabelle is part of the course. All homework proofs must be carried out with Isabelle.
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, 23 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, Fibonacchi heaps
- Disjkstra's algorithm
- String matching
NOTE: This is a new course. At the time of writing it has been submitted to the relevant departmental committee for inclusion in the module catalogue. Approval is expected before the beginning of term. |
|
|
The students must be familiar with
1. Functional Programming (e.g. IN0003 Introduction to Informatics 2) and
2. Discrete Mathematics (e.g. IN0015 Discrete Structures) and
3. Data Structures and Algorithms (e.g. IN0007 Fundamentals of Algorithms and Data Structures) |
|
|
|
|
|
|
|
|
|
|
| Für die Anmeldung zur Teilnahme müssen Sie sich in TUMonline als Studierende*r identifizieren. |
|
| |
| Zusatzinformationen |
|
|
|
|
|
|
