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

Project 2 (Honours version)

Note: The project reports should be done individually.

Range minimim queries in two dimensions

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 (i1,i2,j1,j2) reports the minimum element in A[i1..i2]x[j1..j2]. 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?

Nearest common ancestors under leaf insertions and deletions

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?

Inplace merging

Describe an algorithm that given an array containing n+m elements x1x2...xny1y2...ym, where x1x2≤...≤xn and y1y2≤...≤ym, inplace merges the two sorted sequences. State the running time of your algorithm.

What is the best running time you can achieve?

Prefix counting

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 sum2(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.