Prof. Seth Pettie, assistant professor of Computer Science and Engineering, was recently awarded an NSF CAREER grant for his research project, "Advanced Data Structures for Shortest Paths, Routing, and Self-Adjusting Computation."

The goal of this project is to explore the theory, mathematical underpinnings, and applicability of data structures, primarily in two areas. First, Prof. Pettie intends to design data structures for representing metric spaces and apply metric data structures to solve both online routing problems and long-standing open problems in optimization. Second, he plans to analyze the performance and competitiveness of two self-adjusting data structures, namely splay trees and pairing heaps. While these data structures have defied characterization for more than twenty years, Pettie believes he can make substantial progress on these problems, while applying the self-adjusting design philosophy to new problems.

Pettie believes that the importance of data structures justify a need for increased study in the computer science curriculum, yet sees the role of data structures is being reduced in even the most popular algorithms textbooks. He will develop a course that shows the importance of data structures to modern internet applications. This course will work well within the new program in Informatics offered at U-M, and give students an important introduction to the theory of computer science by focusing on the theory behind many internet applications.

******************

Seth Pettie is a member of the Theory of Computation group in the division of Computer Science and Engineering. His research interests include optimization algorithms, data structures, parallel and distributed computing, graph theory, and combinatorics.

The CAREER grant is one of NSF's most prestigious awards, conferred for "the early career-development activities of those teacher-scholars who most effectively integrate research and education within the context of the mission of their organization."