[8-26]From clear specifications to efficient implementations

Date:2008-08-26

Title: From clear specifications to efficient implementations
Speaker: Prof. Annie Liu( from the Computer Science Department, SUNY Stony Brook, New York)

Venue: Lecture room, Laboratory for Computer Science
Time: 4pm, Tuesday Aug 26
 
Abstract:

Two major concerns of study rest at the center of computer science: what to compute, and how to compute efficiently.  Problem solving involves going from clear specifications for the "what" to efficient implementations for the "how".  This is challenging because clear specifications usually correspond to straightforward implementations, not at all efficient, while efficient implementations are usually difficult to understand, not at all clear.
 
This talk gives an overview of a general and systematic method for transforming clear specifications into efficient mplementations.  The method has three steps: (1) iterate---determine a minimum step to be taken repeatedly, (2)incrementalize---maintain appropriate values incrementally over the repeated steps, and (3) implement---design data structures for the values maintained.  We will illustrate the method through examples, taken from problems in hardware design and image processing expressed using loops and arrays, in query processing and access control expressed using set operations, in sequence processing and math puzzles expressed using recursive functions, in program analysis and trust management expressed using logic rules, and in building software components expressed using objects.  Finally, we summarize our ongoing projects on a number of fronts.