Department of Computer Science Aarhus University Department of Comptuer Science Faculty of Science

Project 1 (Honours version)

Note: The project reports should be done individually.

Exponential search

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?

Merging binary heaps

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?

Finger searches in treaps

Prove that the expected number of nodes in a treap on the path from the finger to the searched key is O(log d).

Counting unique elements in subarrays

Assume given an array A[1..n] of n elements and k pairs (i1,j1)...(ik,jk). 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.