During the course you must handin three projects. The default projects are projects 1-3 below. These are all implementation projects and should be done in groups of 2-3 people. The projects should be documented in reports describing your theoretical considerations, implementation, experiment design and present your experimental results. The evaluation of the reports and implementation will be part of the final grade.
Alternatively, one or two (but not all three) of the projects 1-3 can be replaced by any of the theory projects 4-6 below. Theory projects must be documented by individual reports, i.e. no group reports (you can discuss the theory projects in groups, but the report must be indivual).
Please a.s.a.p. send the names of the people in your group to gerth@cs.au.dk.
The topic of this project is to compare the practical performance of Fibonacci heaps and binary heaps.
The project consists of the following tasks:
The project should be documented in a report. The report should document your theoretical considerations, implementation, experiment design and present your experimental results.
Implementations should preferably be done in C or C++.
In this project you should select one of the below projects.
The topic of this project is to compare the practical performance of van Emde Boas Trees with the priority queue implementations from Project 1 and with Red-Black search trees.
The project consists of the following tasks:
Implementations should preferably be done in C or C++. Elements stored should be 24 bit integers.
The topic of this project is the trade-off between the space usage and query time of different range minimum queries.
The project consists of the following tasks:
Implementations should preferably be done in C or C++. Elements stored should be integers.
In this project you should select one of the below possible projects. Alternatively, if you can define another project related to the course content, you are also welcome to do so. If you wish to do another project than one of the topics listed below, this must be approved before starting the project. Please send the suggestion for an alternative project to gerth@cs.au.dk for approval.
In this project retroactive search trees should be implemented - both partially and fully retroactive search trees. The update operations to the (non-retroactive) search tree should be Insert(x) and Delete(x), and the query operation should be Pred(x) that returns the largest element ≤x stored in the tree. The tasks of the project are to:
In this project the unified dictionary data structure from [BCDI07] should be implemented and compared with other dictionary data structures. The tasks of the project are to:
In this project you should do an experimental study of a functional data structure. Implementations should be done in the lazy functional language Haskell (see www.haskell.org) using the ghc compiler. The tasks of the project are to:
Note: Since Haskell is a lazy functional language, the timing experiments might not be as expected, since the functions called might actually never have been evaluated. To ensure that functions always get evaluated, ensure that you somehow output a result using the result of your computation.
Exponential search traditionally requires 2log d+O(1) comparisons, where d is the number of elements in the range from the finger where the search starts to the position of the searched key. Describe how to perform an exponential search with fewer comparisons. How few comparisons can you perform the search with?
Assume binary heaps are represented by pointers. Describe how to merge two binary heaps of size n and m respectively in polylogarithmic time. What is the best merging time you can achieve?
Prove that the expected number of nodes in a treap on the path from the finger to the searched key is O(log d).
Assume given an array A[1..n] of n elements and k pairs (i_{1},j_{1})...(i_{k},j_{k}). Describe an algorithm that for each of the k pairs (i,j) computes the number of unique elements in A[i..j]. State the running time of your algorithm.
Optional: 1) Consider the static version of the problem where the array A has to be preprocessed so that queries can be answered online. State space, preprocessing time, and query time of your solution. 2) Consider the dynamic version of the problem where the entries of array A are updated online interleaved with queries. State space, update time, and query time of your solution.
Let A be a two dimensional array of size n x m. Describe how to preprocess A into a data structure that given a rectangular query range given by (i_{1},i_{2},j_{1},j_{2}) reports the minimum element in A[i_{1}..i_{2}]x[j_{1}..j_{2}]. State the space, preprocessing time, and query time of your data structure.
Optional: What is the best space bound you can achieve with O(1) query time? What is the best query time you can achieve with O(nm) space?
Describe a data structure to maintain a tree T under the insertion and deletion of leafs (to insert a new leaf we are given a pointer to the parent node), while supporting nearest common ancestor queries of two arbitrary nodes in T. State the update and query time of your data structure.
What are the best update and query bounds you can achieve?
Describe an algorithm that given an array containing n+m elements x_{1}x_{2}...x_{n}y_{1}y_{2}...y_{m}, where x_{1}≤x_{2}≤...≤x_{n} and y_{1}≤y_{2}≤...≤y_{m}, inplace merges the two sorted sequences. State the running time of your algorithm.
What is the best running time you can achieve?
Let A be an array of size n, where each A[i] is either 0 or 1. Describe a data structure that supports updating an entry of A to either 0 or 1, and the query sum_{2}(i) that returns (A[1]+A[2]+...+A[i]) mod 2, ie. decides if the sum of the first i entries of A is odd or even.
What is the best query time and update time you can achieve? A lower bound of Ω(log n/log log n) is known for the operations on the RAM.
Optional: Generalize the construction to return the sum A[1]+A[2]+...+A[i], ie. the number of entries equal one among the first i entries.
Prove that fully retroactive queues must require time at least time Ω(log m/loglog m) on a RAM. Hint: give a reduction from the parity problem (considered in Project 5) to the fully retroactive queue problem ([Fredman & Saks, STOC 1989]).
Describe a data structure supporting the following three operations in worst-case constant time:
The operations may use a procedure alloc(n) that in worst-case constant time returns an uninitialized array of length n, where each cell contains O(log n) bits, i.e., all entries of the allocated array contain random information.
Describe a (strict) functional data structure supporting the operations push(x), pop(), and lookup(d), i.e. a functional stack supporting the lookup of the dth element. A normal list will support the operations in time O(1), O(1) and O(d) time respectively, whereas a balanced tree will achieve O(log n) time for all three operations, where n is the size of the list. Can you achieve the best of both worlds?
In the description of maxiphobic heaps [Okasaki 2005, Section 3] it is stated:
Finally, note that "size" in maxiphobic heaps can be interpreted as either number of nodes or height of the tree. Either interpretation leads to a successful solution
Describe and analyse a solution of maxiphobic heaps based on height.