Associate Professor of Computer Science; Chair of Computer Science Department
Searles Science Building - 219
An introductory course on the design and analysis of algorithms. Introduces a number of basic algorithms for a variety of problems such as searching, sorting, selection, and graph problems (e.g., spanning trees and shortest paths). Discusses analysis techniques, such as recurrences and amortization, as well as algorithm design paradigms such as divide-and-conquer, dynamic programming, and greedy algorithms.
Geographic information systems (GIS) handle geographical data such as boundaries of countries; course of rivers; height of mountains; and location of cities, roads, railways, and power lines. GIS can help determine the closest public hospital, find areas susceptible to flooding or erosion, track the position of a car on a map, or find the shortest route from one location to another. Because GIS deal with large datasets, making it important to process data efficiently, they provide a rich source of problems in computer science. Topics covered include data representation, triangulation, range searching, point location, map overlay, meshes and quadtrees, terrain simplification, and visualization.
I am interested in I/O-efficient algorithms and data structures, in particular in I/O-efficient graph algorithms and applications to Geographic Information Systems (GIS).
A significant part of my work has been motivated by scalability issues in Geographic Information Systems (GIS). I am interested in developing new methods and algorithms for representing, modeling, and analyzing massive terrain data in GIS. I am interested in algorithms that are not only of theoretical interest, but perform well in practice and scale to very large inputs, using techniques from I/O-efficient algorithms and cluster computing.