2. Environments for Combinatorial Computing

• Implementing Discrete Mathematics: Combinatorics and Graph Theory in Mathematica, Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990. ISBN number 0-201-50943-1. Japanese translation published by Toppan, Tokyo, July 1992.

Combinatorica is a combinatorial computing environment we have developd which has been widely used to support research and teaching in discrete mathematics. Combinatorica received a 1991 EDUCOM Higher Education Software Award. Written in Mathematica, it comprises over 230 functions for constructing and displaying graphs, constructing other combinatorial objects such as permutations, partitions, and Young tableaux, and computing properties of these structures.

We have recently begun a project to produce a updated version of Combinatorica, with superior algorithmic performance and improved graphical interface.

• The Algorithm Design Manual, Telos/Springer-Verlag, New York, 1998.

• Who is interested in algorithms and why?: lessons from the Stony Brook Algorithms Repository. Second Workshop on Algorithm Engineering, Saarbrucken, Germany, August 20-22, 1998. Also, ACM SIGACT News, September 1999.

This project is an ongoing effort to collect and catalog algorithm implementations, and systematize the process of algorithm design. It is described in my book, which includes a multimedia CD-ROM integrating sound, images, source code, and text.

The associated Stony Brook Algorithms Repository (http://www.cs.sunysb.edu/$\sim$algorith) now receives well over 400,000 hits per year. By analyzing the hits, we can determine the relative interest among 75 fundamental algorithmic problems. This ``market research'' can guide to researchers in algorithm engineering to focus on the most needed and important problems.

The Stony Brook Algorithm Repository was recently invited to become part of the ACM Digital Library.

• VType: Text Entry in an Immersive Virtual World (with F. Evans and A. Varshney), Submitted to Int. Journal of Human-Computer Studies.

• Sentence Reconstruction using Word Ambiguity Resolution, (with Harald Rau). U.S. Patent 5,828,991. Issued October 27, 1998.

• Dialing for Documents: an Experiment in Information Theory (with Harald Rau). Journal of Visual Languages and Computing 7 (1996) 79-95.

Standard telephone keypads are labeled with letters of the alphabet, enabling users to enter textual data for a variety of possible applications. However, the overloading of three letters on a single key creates a potential ambiguity as to which character was intended, which must be resolved for unambiguous text entry. Existing systems all use pairs of keypresses to spell out single letters, but are extremely cumbersome and frustrating to use. Instead, we propose single-stroke text entry on telephone keypads and other overloaded keyboards, with the ambiguity resolved by exploiting information-theoretic constraints. We develop algorithms capable of correctly identifying up to 99% of the characters in typical English text, sufficient for such applications as telephones for the hearing-impaired, data entry in virtual reality systems, E-mail without a terminal, and advanced voice-response systems.