This CAREER project focuses on both research and educational goals. The research component of this project addresses fundamental questions in interactive systems such as programming environments or on-line access to travel services. A key factor for the success of interactive systems lies in their speed and, thus, in efficient algorithms for interactively handling requests. One powerful paradigm in the design of efficient algorithms is to reduce the amount of recomputation by storing essential information gathered during earlier computational steps in a suitable data structure for later use. In interactive situations an additional difficulty arises: The problem instance changes incrementally, which requires dynamic data structures. While efficient dynamic data structures are widely used, efficient dynamic data structures for graphs are still in the research phase. This project includes the following research goals: (1) Design of dynamic data structures which exploits recent progress in using approximation and randomization in the design of graph algorithms; (2) Applications of dynamic data structures to improve the efficiency of algorithms for incrementally changing problems. These applications can be used on problems which do not necessarily fit the dynamic framework. For example, using dynamic techniques, a faster algorithm for the consensus tree problem is explored. This algorithm has applications in computational biology and in the theory of databases; (3) Implementation of dynamic data structures for graphs, which extends the widely-used Library of Efficient Data Types and Algorithms (LEDA). The Educational Component of this CAREER Grant includes the goals in undergraduate and graduate education: (1) At the undergraduate level a basic goal is to redesign the senior-level algorithms course to teach the use of efficient advanced data structures by asking for implementations of algorithms in homework assignments and projects using LEDA; (2) A second basic goal is to promote the advancement of women engineers by: Counseling and mentoring female students; Giving presentations to industry and students; Participating in workshops which are sponsored by Cornell University's outreach program, Expanding Your Horizons Program, for (female) middle school students.
