Title:From clear specifications to efficient implementations

Speaker:Prof. Annie Liu

Time:4:00pm, Tuesday£ĴAug.26

Venue:Lecture Room,State Key Lab of Computer Science, Level 3 Building #5, Institute of Software, CAS


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 implementations. 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.