This repository contains the code and reports thatjointly constitute the compulsory projects of the AA course at Aarhus University, nicknamed dADS3, that ran in the fall of 2013.
The work herein was done jointly with Troels Leth-Jensen and Morten Krogh-Jespersen under the supervision of Prof. Gerth S. Brodal.
Project 1 compares traditional (almost historical!) array-based binary heaps with Fibonacci heaps, both done in C.
Project 2 compares another traditional data structure, the Red-Black Tree with a modern counterpart, van Emde Boas Trees. Implementations are in C.
Project 3 compares the performance of various purely-functional, some lazy, implementations of queues in Haskell, notably the venerable Hood-Melville queue as interpreted by Chris Okasaki. The implementations are (mostly) verified in Coq, and all the code is extracted from the include proof script (which marks the first time I have certified my homework!).