Robert Sedgewick - US grants

A new Department of Computer Science has been formed at Princeton University; unusually outstanding new faculty members have been and are continuing to be recruited at all levels to join a nucleus of individuals from the former Department of Electrical Engineering and Computer Science. With the support provided by the University, this Institutional Infrastructure award will aid in the establishment and operation of a research computing environment that can serve as the basis for experimental computer science research activities at Princeton into the next decade. Research at Princeton includes work in Programming Languages, Graphical Representations of Mathematical Objects, VLSI Layout Algorithms and Tools, Design and Analysis of Data Structures, and Algorithm Animation. The facility to be provided, which includes high-performance workstations and advanced personal computers will, with the primary VAX equipment provided by the University, serve the needs of all of these diverse projects, allow the current group to move forward in experimental research and provide for additional planned growth of both faculty and students.

The goal of this research is to understand the performance characteristics of fundamental algorithms that are likely to be broadly applicable. The primary focus is on analytic techniques that can result in precise performance predictions, on essential characteristics of specific implementations and their impact on practical situations, and on tools that can help uncover important properties of algorithms. Not all algorithms can be analyzed to the point that we can accurately predict their performance (indeed, most cannot). It is precisely for this reason that much algorithm design is done at the "complexity" level, where characteristics of machines, implementations, and input models can be ignored in the search for an algorithm with good or "optimal" worst-case performance characteristics. Research from this approach has mushroomed in recent years: scores of fundamental new algorithms for a wide variety of new and old applications have been devised. Unfortunately, it is too often the case that such algorithms are not useful in practice, because they have intricate worst-case avoidance mechanisms that add to overhead. This research will continue the study of methods that prove empirically to be useful in practice, to focus design efforts on improving the performance of such methods or devising demonstrably better methods, and to focus analysis efforts on techniques that can accurately predict performance.

The prime goal of this research is to understand the performance characteristics of fundamental algorithms that are likely to be broadly applicable. Considerations include analytic techniques that can result in precise performance predictions and essential characteristics of specific implementations and their likely impact in practical applications. A goal is to be able to make intelligent choices among existing algorithms for the same task and to have a reasonable basis for developing new, better algorithms. Visual presentations of information can be an important tool in the study of algorithms. The emphasis in this project is on exploiting recent developments in printing technology to enable the design of information-rich visual representations that can effectively exhibit essential properties of algorithms, and on using such representations as an integral part of an ongoing research program in the design and analysis of combinatorial algorithms.//