Design and Analysis of Algorithms

Modern applications of computer science ultimately depend on having highly efficient algorithms for solving basic computational tasks; some examples are searching and summarizing a large corpus of textual data, finding optimal routes in networks, or finding an optimal solution to a set of linear inequalities. Efficiency is a fine goal, but what is it exactly? We try to characterize, in a mathematically rigorous way, the computational resources (running time, storage space, communication, energy, etc.) required to solve various combinatorial and optimization problems. We also investigate how changing the model of computation affects the complexity of solving specific problems. For example, we now know that quantum computers could solve some problems exponentially faster than a classical computer and that many other, but not all, problems can be solved significantly faster on a parallel computer.

Algorithms research at Michigan spans across many areas, including network optimization, approximation algorithms, the design and analysis of data structures, combinatorial problems in geometry, analysis of social networks, and algorithms for various parallel, distributed, and streaming models of computation.

CSE Faculty

Pettie, Seth
Stout, Quentin F.
Volkovich, Ilya