Algorithm Engineering for
Fundamental Data Structures and Algorithms

Algorithm engineering views design, analysis, implementation, and experimental analysis of algorithms as an integrated process in the tradition of Popper's scientific method. This mini course discusses the application of this process to algorithms for fundamental data structures and algorithms. The course begins with an in-depth discussion of several aspects of sorting with particular emphasis on advanced models of computations: Why are comparisons so expensive and can this be changed? How to sort using many disks? As a natural generalization the course then proceeds to priority queues that are efficient in context of memory hierarchies.

The remainder of the course is made up of several loosely coupled modules that will be treated depending on time and the interestes of the participants:

• Efficient sorting of the suffixes of a string (e.g., to get a full text index)
• Exploiting integer keys to speed up search trees
• Space efficient hash tables with worst case constant access time.
• Several aspects of algorithms for miminum spanning trees most of which are related to data structures.
  • Implementation details of the Jarník-Prim algorithm and Kruskals algorithm
  • Kruskal's algorithm reconsidered
  • Practical algorithms that use the cycle property to filter out edges
  • Practical external memory algorithms

The following annotated bibliography lists papers and other ressources that can be used as background reading.

Here is a preliminary version of the slides (June 15, 2004) .ps.gz .pdf

Bibliography

1

R. Fleischer, B. Moret, and E. Meineche Schmidt, editors.
Experimental Algorithmics, volume 2547 of LNCS State-of-the-Art Survey.
Springer, 2002.

A collection of papers on algorithm engineering, including papers on methodology.

2

P. Sanders and S. Winkel.
Super scalar sample sort.
In 12th European Symposium on Algorithms, LNCS. Springer, 2004.

This paper explains the sorting algorithm explained in Section 1 of the course.

3

D. E. Knuth.
The Art of Computer Programming -- Sorting and Searching, volume 3.
Addison Wesley, 2nd edition, 1998.

A standard book on sorting and searching. Section 5.4.9 explains multiway merging, run formation, and the mechanism of predicting block accesses. The second edition also covers parallel disk sorting using an earlier approach. Question Exercise 5.4.9-31 asks for a tighter analysis of this earlier algorithm and puts the answer at difficulty 48 on a scale between 1 and 50. Our algorithm can be viewed as a positive answer to this question albeit using a different (better) algorithm.

4

R. Dementiev and P. Sanders.
Asynchronous Parallel Disk Sorting.
In 15th ACM Symposium on Parallelism in Algorithms and Architectures, pages 138-148, San Diego, 2003.

This paper decribes the parallel disk sorting algorithm developed in Section 2. The emphasis is on overlapping I/O and computation and experiments. The theory behind the optimal prefetching algorithm and its probabilistic analysis is developed in several previous papers cited there.

5

R. Dementiev.
<stxxl>.

Look at http://www.mpi-sb.mpg.de/~rdementi/stxxl.html for the latest news on the <stxxl> library for external computing that is used for the experiments on parallel disk sorting in Section 2 and external minimum spanning trees in Section 6. The library also contains an external memory implementation of the priority queue discussed in Section 3.

6

P. Sanders.
Fast Priority Queues for Cached Memory.
ACM Journal of Experimental Algorithmics, 5, 2000.

Discussion of the priority queue introduced in Section 3. The implementations are tuned for caches and main memory rather than disks.

7

J. Kärkkäinen and P. Sanders.
Simple Linear Work Suffix Array Construction.
In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS, pages 943-955, 2003.

Describes the theory and a simple implementation of an optimal algorithm for suffix array construction. Stay tuned for upcoming more detailed papers and external memory implementations.

8

Kurt Mehlhorn and Stefan Näher.
Bounded ordered dictionaries in $O(\log \log N)$ time and $O(n)$ space.
Information Processing Letters, 35(4):183-189, 1990.

9

R. Dementiev, L. Kettner, J. Mehnert, and P. Sanders.
Engineering a sorted list data structure for 32 bit keys.
In Workshop on Algorithm Engineering & Experiments, New Orleans, 2004.
The tuned implementation of search trees with 32 bit integer keys described in Section 4.

10

D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis.
Space efficient hash tables with worst case constant access timefull paper.
In 20th International Symposium on Theoretical Aspects of Computer Science, number 2607 in LNCS, pages 271-282, Berlin, 2003. Springer.

The paper behind Section 5.

11

B.M.E. Moret and H.D. Shapiro.
An empirical assessment of algorithms for constructing a minimum spanning tree.
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 15:99-117, 1994.

12

I. Katriel, P. Sanders, and J. L. Träff.
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property.
In 11th European Symposium on Algorithms (ESA), number 2832 in LNCS, pages 679-690. Springer, 2003.

The algorithm described in Section 6.2.

13

T. M. Chan.
Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees.
Information Processing Letters, 67(6):303-304, 30 September 1998.
An elegant analysis of the sampling lemma used in Section 6.1-6.4.

14

R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn.
Engineering an external memory minimum spanning tree algorithm.
In 3rd IFIP International Conference on Theoretical Computer Science, 2004.

The node reduction algorithm from Section 6.4 and the external algorithm described in Section 6.5.