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."