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
- 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
time and
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.
Peter Sanders
2004-06-07