Speaker:
Dr. Carla Savage, Computer Science, NCSU
Abstract:
Many practical problems require for their solution the sampling of a
random object from a combinatorial class or, worse, an exhaustive
search through all objects in the class. However, in order for such
a listing to be possible, even for objects of moderate size, combinatorial
generation methods must be extremely efficient. The ``Gray code''
approach is to try to generate the objects as a list in which successive
elements differ only in a small way. The classic example is the binary
reflected Gray code which is a scheme for listing all $n$-bit binary
numbers so that successive numbers differ in exactly one bit. The
advantage anticipated by such an approach is that generation of successive
objects might be faster. Although for many combinatorial families, a
straightforward lexicographic listing algorithm requires only constant
average time per element, for other families, such as linear extensions,
such performance has only been achieved by a Gray code approach.
Aside from computational considerations, open questions in several areas
of mathematics can be posed as Gray code problems. Gray codes frequently
involve elegant recursive constructions which provide new insights into
the structure combinatorial families.
In this talk, we survey the area of combinatorial Gray codes, describe
recent results, variations, and trends, and highlight some open problems.
Short Bio:
Carla Savage is currently a Professor in the Department of Computer
Science at NCSU, where she joined the faculty in 1978. She worked in
the area of parallel algorithm design for her Ph.D. thesis
(Mathematics, University of Illinois 1977) and for the ten years
following. Her research since 1988 has been in the areas of discrete
mathematics and combinatorial algorithms. The focus has been on
the structure of combinatorial objects and various schemes for listing and
counting them, with particular emphasis on efficient computation, Gray codes,
and relationships to problems in graph theory, group theory, and
combinatorics. Recent work is on identities and asymptotics for various
classes of integer partitions. The work has been supported, by grants
from NSF and NSA, in some combination, over the past ten years.
Savage is on the editorial board of the SIAM Journal on Discrete Mathematics.
In recent years, she has served as Vice Chair of the SIAM Activity Group
on Discrete Mathematics (1993-96), Chair of the Steering Committee for the
SODA Conference (1995-98), and on the program committees for the 1998 SIAM
Conference on Discrete Mathematics and the 1999 SIAM Annual Meeting.