Seminar Topics: Summer Semester 2018

For the Software Engineering Seminar we offer the topics below.

Persistence

Topic 1: Red-black trees
- PFDS 3.3
- Red-black trees in a functional setting
  Chris Okasaki
  JFP 9(4), 1999
- Deletion: The curse of the red-black tree
  Kimball Germane, Matthew Might
  JFP 24(4), 2015
Topic 2: 1-2 Brother trees
- Purely functional 1-2 brother trees
  Ralf Hinze
  JFP 19(6), 2009
Topic 3: Binary heaps
- PFDS 3.1
- 1.1–1.4 of Fun with binary heap trees, Chris Okasaki, in Jeremy Gibbons, Oege de Moor, editors, The Fun of Programming

Topic 4: Queues
- PFDS 6, 6.2.1, 6.3.2, 6.4.2
- Simple and efficient purely functional queues and deques
  Chris Okasaki
  JFP 5(4), 1995
Topic 5: Lazy skew heaps
- 1.5–1.7 of Fun with binary heap trees, Chris Okasaki, in Jeremy Gibbons, Oege de Moor, editors, The Fun of Programming

Topic 6: Random-access lists
- PFDS 9.2.1, 10.1.2
- Purely Functional Random-Access Lists
  Chris Okasaki
  Conference on Functional Programming Languages and Computer Architecture (FPCA), 1995
Topic 7: Binomial heaps
- PFDS 6.4.1
- Explaining binomial heaps
  Ralf Hinze
  JFP 9(1), 1999
Topic 8: Constructing Red-black Trees
- Constructing Red-black Trees
  Ralf Hinze
  Workshop on Algorithmic Aspects of Advanced Programming Languages (WAAAPL), 1999

Topic 9: Catenable Lists
- PFDS 10.2.1
- Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking
  Chris Okasaki
  36th Annual Symposium on Foundations of Computer Science (FOCS), 1995
Topic 10: Optimal Heaps
- PFDS 10.2.2
- Optimal Purely Functional Priority Queues
  Gerth Stølting Brodal, Chris Okasaki
  JFP 6(6), 1996
Topic 11: Flexible Arrays
- Bootstrapping one-sided flexible arrays
  Ralf Hinze
  International Conference on Functional Programming (ICFP), 2002