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.
Computational geometry studies algorithms for collections of geometric objects such as points, lines, polygons. For example: given a set of locations, find the closest pair of locations; find a triangulation of a set of surface samples that maximizes the minimum angle of a triangle -- this type of meshing is often used in solid modeling, where small angles cause numerical instability; find whether two polygons intersect. Geometric algorithms arise in areas such as computer graphics, robotics, or image processing. Covers the basic geometric problems and techniques: polygon triangulations, convex hulls, Delaunay triangulations and Voronoi diagrams, visibility, geometric searching, and motion planning. Class work consists of a set of programming assignments in C/C++.
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.