DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

Candidate: Deepak Goyal

Advisor: Bob Paige

DOCTORAL DISSERTATION DEFENSE

Candidate: Deepak Goyal

Advisor: Bob Paige

**A Language-Theoretic Approach To Algorithms**

10:00 a.m., Friday, October 15, 1999

12th floor conference room

719 Broadway

Abstract

An effective algorithm design language should be 1) wide-spectrum in nature, i.e. capable of expressing both abstract specifications and low-level implementations, and 2) "computationally transparent", i.e. facilitate accurate estimation of time and space requirements. The conflict between these requirements is exemplified by SETL which is wide-spectrum, but lacks computational transparency because of its reliance on hash-based data structures. The first part of this thesis develops an effective algorithm design language, and the second demonstrates its usefulness for algorithm explanation and discovery.

In the first part three successively more abstract set-theoretic languages are developed and shown to be computationally transparent. These languages can collectively express both abstract specifications and low-level implementations. We formally define a data structure selection method for these languages using a novel type system. Computational transparency is obtained for the lowest-level language through the type system, and for the higher-level languages by transformation into the next lower level. We show the effectiveness of this method by using it to improve a difficult database query optimization algorithm from expected to worst-case linear time. In addition, a simpler explanation and a shorter proof of correctness are obtained.

In the second part we show how our data structure selection method can
be made an effective third component of a transformational program
design methodology whose first two components are finite differencing
and dominated convergence. Finite differencing replaces costly
repeated computations by cheaper incremental counterparts, and
dominated convergence provides a generalized iteration scheme for
computing fixed-points. This methodology has led us to a simpler
explanation of a complex linear-time model-checking algorithm for the
alternation-free modal mu-calculus, and to the discovery of an
*O*(*N*^{3}) time algorithm for computing intra-procedural may-alias
information that improves over an existing *O*(*N*^{5}) time algorithm.