Advanced Algorithms - Data Structures (Fall 2005)

Project 2

The topic of this project is to solve four theoretical problems. The project should be done in groups of 2-3 people. The project should be documented in a report that is due Wednesday December 14, 14.15, 2005.

Problem 1 (union-find)

In the union-find problem, show that any sequence of m make-set, union, and find operations, where all the union operations appear before any of the find operations, takes only O(m) time if both path compression and union by size (i.e. linking the smaller tree to the larger one in each union are used) are used. What happens if only the path compression heuristic is used?

Problem 2 (ancestor queries in trees)

Suppose that instead of least common ancestor queries in a 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 3 (planar separators)

The planar separator theorem gives 1/3-2/3 separators of size O(sqrt(n)) for arbitrary planar graphs. Show that this is the best you can do in general, i.e., give a family of planar graphs whose smallest 1/3-2/3 separators are of size Omega(sqrt(n)).

Problem 4 (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.