Colloquium Details
Certifying Algorithms and the Undergraduate Curriculum
| Author: | Ross McConnell Colorado State University |
|---|---|
| Date: | June 05, 2008 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
A proof of correctness of an algorithm is no guarantee that an implementation of it has no bugs. Software engineers typically try to reduce the probability of bugs through extensive testing, but this does not supply certainty. An alternative is a detailed proof that the implementation is correct, but such a proof, being even more complicated than the program it addresses, can be even more prone to human error.
The topic of the talk is a third approach, largely ignored until recently. It sidesteps entirely the issue of whether an implementation has any bugs, focusing instead on whether a particular output has been compromised by one.
An algorithm is "certifying" if it returns with each output a simple certificate that the particular output is correct. Many well-known problems that are complicated to solve nevertheless give rise to simple-to-check certificates, but the issue of designing algorithms to produce them has been largely overlooked.
In our opinion, finding certifying algorithms should be promoted as a desirable algorithm design philosophy. The talk will survey how most of the algorithms commonly presented in undergraduate algorithms courses can be redesigned to produce certificates.
Biography
Ross McConnell is Associate Professor in the Computer Science Department, with a joint appointment in the Math Department, at Colorado State University at Fort Collins. He got his Ph.D. at the University of Colorado at Boulder in 1994, his M.S. at the University of Denver, and his B.A. at Williams College. His research interests focus primarily on graph-theoretic algorithms.