Advanced Algorithms - Data Structures (Fall 2007)

Project 2

The topic of this project is to solve five theoretical problems. The project should be done in groups of 2-3 people. The project should be documented in a report that is due Thursday November 22, 14.15, 2007.

Problem 1 (ancestor queries in trees)

Suppose that instead of least common ancestor queries in a static tree, we only need to answer ancestor-descendant queries: is node x an ancestor of a node y? Describe a simple space-efficient data structure supporting these queries in constant time.

Problem 2 (array initialization)

Describe a data structure supporting the following three operations in worst-case constant time:

Init(n) create a "list" L of length n with all entries set to nil.
Set(i,v) set the ith entry of L to v.
Get(i) return the ith entry of L.

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.

Problem 3 (temporal local dictionaries)

Describe a comparison based dictionary data structure that stores n elements. The data structure should support the two operations:

Init(x₁,...,x_n), that initializes the data structure with n elements, and
Find(x) that localizes x in the stored set.

The Find(x) operation should be supported in time O(log d), where d is the number of distinct elements accessed since the last access to x. The first access to an element should be supported in time O(log n). The time bounds can be amortized or worst-case.

Problem 4 (planar graph representation)

Show how to represent an undirected planar graph G=(V,E) in O(V) space such that queries "is (u,v) in E?" can be answered in constant time. (The solution should not use hashing.)

Problem 5 (trekking in the Alps)

Suppose we are given a map consisting of a set of valleys in the Alps with high mountain passes connecting the valleys. We wish to plan a route from a starting valley to a destination valley, keeping the maximum altitude on the path as low as possible. It is known that an optimal solution to this problem can be found by computing a minimum spanning tree on a graph with one vertex per valley and one edge per pass, and following a path in this minimum spanning tree. We wish to design a data structure that can tell us the maximum altitude reached on the optimal path between any specified pair of valleys. Describe a space-efficient data structure that can answer queries in constant time per query.

This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>