COMPUTER SCIENCE DEPARTMENT

This was a record-breaking year for the Computer Science Department. On June 8, we celebrated the graduation of 26 senior majors, our largest class yet. With the addition of our newest colleague, Steve Freund, this past academic year also saw us reach a record size of eight full-time faculty. Our computing facilities continue to expand, with our facilities manager, Mary Bailey, deploying an ever-increasing array of workstations and software tools in her tireless efforts to meet the diverse curricular and research needs of our students and faculty. And, of course, Lorraine Robinson, our administrative assistant, continues daily to provide invaluable support to all.

Professors Bruce, Danyluk and Murtagh, continued their work on developing new materials for the innovative introductory course developed and taught at Williams over the last several years. This work is supported by a $287,892 grant from the NSF CCLI program. This new approach uses Java as the programming language, and places a heavy emphasis on event-driven programming and concurrency early in the course. The grant supports the writing of a textbook for this course as well as further refinement of the “objectdraw” library and other supporting software for the course. Peter Applegate ‘03 worked with the faculty on software for the course in the summer of 2002, and Ashok Pillai ’05 will continue that work in the summer of 2003. In the summer of 2002, 15 faculty members from other colleges and universities attended a four-day workshop on using these materials, and have been using the materials this year. Professors Bruce, Danyluk and Murtagh have now signed a contract with Prentice-Hall on the book, with the final manuscript due in November.

This year Professor Duane Bailey began using the second edition of his text, Java Structures, a basic text on data structures, written for the Java programmer. He has begun work on revision of the software for the next generation of Java compilers, which he hopes to have available for use in fall of 2003.

Professor Bailey is continuing his investigation of computer science problems relating to the mechanics of genetics and molecular biology. He is also writing software that will support a winter study investigation of the ideas common to biology and computer science. That software should be freely available on the web by the end of the summer. The new course, Life as an Algorithm, will be offered in 2004, and may join the regular offerings of the department a year or two later.

Professor Kim Bruce continued his research on the type theory and semantics of object-oriented languages. The overall goal of his research is to increase the understanding of the key concepts of object-oriented languages in order to promote the design of more secure and expressive object-oriented languages. His research continues to be support by the National Science Foundation. He and Professor Stephen Freund were awarded a 3-year NSF research grant beginning in July 2003.

Research continued on three main projects. The first involved the design and implementation of an extension of Java that supports parametric polymorphism and a “ThisType” construct. Most of the work on that project this year was accomplished with Robert Gonzalez ’03, who worked as a research assistant during the summer of 2002, and also wrote an honors thesis on his further research during the academic year. John “Nate” Foster ’01 also consulted on the project and helped Rob understand the changes to the Java compiler that were part of Nate’s earlier thesis. Rob’s main work was on a modification of Sun’s Java virtual machine to increase the safety of the virtual machine when dealing with the new language features. His work also increased the efficiency of programs run with the virtual machine. Rob will be continuing this work as a research assistant during the summer of 2003.

The second project involved further work on the module system for LOOM, an object-oriented language developed at Williams with the assistance of several students. Diane Bennett worked as a research assistant for this project during the summer of 2002 and continued her work in a research course during the fall term of 2002. Her work resulted in a design for further improvements to LOOM’s module system, originally designed by Professor Bruce and Leaf Petersen ‘96. We hope to make further progress on this in the near future with another student.

The third project involved further work on providing type systems that support concurrent extension of mutually referential systems of interfaces and classes. This work built on research undertaken earlier with Joe Vanderwaart ’88. Increases in the sophistication of the type system has enabled a larger number of programs to be type-checked, and work is continuing on developing more expressive type systems that will guarantee that more relations in the original group of types will be preserved under extensions.

Professor Bruce was a co-organizer of the ECOOP 2002 Sixth Workshop on Pedagogies and Tools for Learning Object-Oriented Concepts in Malaga, Spain, in June 2002, and is co-organizing a similar workshop at ECOOP 2003 in Germany in July 2003. He chaired the meeting of the Liberal Arts Computer Science Consortium at Grinnell College. He also was on the program committee for POPL ’03, held in New Orleans in January 2003.

Professor Bruce was involved in several other activities through the last academic year. He served as outside evaluator in a tenure case this fall. He served on a visiting committee for Computer Science at Pomona College in April 2003. He attended the ECOOP 2002 meeting in Malaga, Spain in June 2002, the POPL ‘03 and FOOL 9 meetings in New Orleans in January 2003, and the ETAPS conferences in Warsaw, Poland in April 2003. He gave a talk at the New England Programming Languages Seminar at Yale University in August 2003, gave a seminar at the University of Turin in Turin, Italy, and gave an invited lecture at the Workshop on Object-Oriented Developments in Warsaw, Poland. Finally, he gave a tutorial on the Foundations of Object-Oriented Languages at ECOOP 2002 in Malaga, Spain.

On campus, he served as chair of the Faculty Steering Committee for 2002-2003, and was elected to serve on the Committee on Appointments and Promotions starting July 2003. He also gave a talk on his research to the Science Bag Lunch in November 2002.

This past year Professor Danyluk enjoyed a year of being on leave. During her leave, she gave an invited technical talk at the Fourth Grace Hopper Celebration of Women in Computing, which was held in Vancouver in October. The work that she presented was also published in the Handbook of Data Mining and Knowledge Discovery, which was published by Oxford University Press in 2002.

In the summer of 2001, Professor Danyluk, together with Professor Carla Brodley of Purdue University, co-chaired the Eighteenth International Conference on Machine Learning. Professors Danyluk and Brodley edited a special issue of the Journal of Machine Learning Research that includes a collection of work that grew out of that conference. The special issue came out in December 2002. This year Professor Danyluk is a member of the Advisory Committee for the Twentieth International Conference on Machine Learning. She has served as a reviewer for the Machine Learning Journal as well as the Doctoral Consortium to be held at the Eighteenth International Joint Conference on Artificial Intelligence in July 2003.

This fall, Professor Danyluk will be a member of the program committee for a Special Track on AI Education, to be held in conjunction with FLAIRS-03, the Florida AI Research Symposium.

Assistant Professor Stephen Freund came to Williams College in the summer of 2002. Since then, he has continued his research on automated tools for improving software reliability. The overall goal of this research is to improve software quality by designing tools to identify certain types of errors in programs before they are deployed to the public. Most recent work has focused on race conditions in concurrent programs. He presented a paper on “Thread-Modular Verification for Shared Memory Programs” at the European Symposium on Programming in Grenoble, France. This was joint work with Cormac Flanagan (HP Labs) and Shaz Qadeer (Microsoft Research)). He also presented a paper at the International Conference on Compiler Construction in Warsaw, Poland.

In the fall, Professor Freund gave talks on his work at Brown University, the New England Programming Languages Seminar (held at Yale), and the Workshop on Lightweight Languages (at MIT). In addition to those workshops and conferences, he attended the Symposium on Principles of Programming Languages in New Orleans in January, the IBM Programming Languages Seminar, and the New England Programming Languages Seminar at WPI in October. Most recently, he visited HP Labs and Microsoft Research to collaborate with colleagues at those institutions on ongoing research projects.

Professor Freund served as an external reviewer for the Symposium on Principles of Programming Languages, Conference on Programming Language Design and Implementation, Symposium on Operating Systems Principles, Journal of Automated Reasoning, Proceedings of the Estonian Academy of Sciences, and Transactions on Programming Languages and Systems.

During the summer of 2003, Professor Freund will be working with Peter Applegate, class of ’03, to build a type inference engine for a tool that checks atomicity specifications in Java programs, and with Professor Bruce and Rob Gonzalez, class of ’03, on module systems for object-oriented languages.

Assistant Professor Barbara Lerner was on leave during 2002-2003. While on leave, she continued her research into the coordination of human and automated agents. The recent focus of her work has been to use software verification tools and consistency checking tools to analyze coordination processes written in the language Little-JIL.

During summer 2002, Professor Lerner worked with Shimon Rura (‘03) using xlinkit, a consistency checking tool, to develop an analyzer for Little-JIL processes that detects semantic errors and programming anomalies. Using xlinkit, semantic rules are described declaratively in first-order logic. This novel approach to specifying language semantics resulted in rules that were well encapsulated and easier to understand than traditional implementations of semantic checkers. The rules defined ranged from simple localized rules, such as ensuring that variables were initialized, to more complex rules, such as detecting cases of infinite recursion.

Shimon also worked with Professor Lerner on an honors thesis studying the refactoring of aspect-oriented software. Aspect-oriented software is a new approach to software development in which features that apply to multiple classes are encapsulated within their own constructs, called aspects, and woven into those classes at execution points defined within the aspects. Refactoring is a software development methodology used to reorganize the code in a piece of software to facilitate its maintenance without changing its behavior. Both aspect-oriented approaches and refactoring are thus aimed at modifying the encapsulation of software to improve its maintainability. Shimon’s thesis involved studying how these techniques can interact. Specifically, he investigated how existing refactorings for object-oriented languages must be changed to work with aspects and also what new refactorings would better support the development of aspect-oriented software.

Professor Bill Lenhart continued to pursue his research interests in graph algorithms and computational geometry. This year he supervised the honors work of Jeremy Redburn ’03. Jeremy’s project focused on the design of efficient algorithms for the exact (that is, free of numerical error) computation of visibility information from certain kinds of 3-dimensional graphics scenes.

The paper “Bichromatic P4 Composition Schemes for Perfectly Orderability”, written with Professor Ryan Hayward of the University of Alberta, was recently accepted for a special issue of the journal Discrete Applied Mathematics dedicated to the conference Brazilian Symposium on Graphs, Algorithms and Combinatorics 2001 in Fortaleza, Brazil.

This summer Professor Lenhart will be attending the 2003 PIMS-MITACS Summer School on Quantum Information Science at the University of Calgary, as well as the ACM SIGGRAPH conference on computer graphics in San Diego.

Professor Lenhart served as chair of the department again this year; he also served as the Division III representative on the Committee on Appointments and Promotions. As of June 30, he will be stepping down from both of these positions to assume the role of Acting Dean of the Faculty until January 2004, at which time he is scheduled to take what he expects will be a much-needed sabbatical.

Professor Murtagh continued to investigate the behavior of the congestion control mechanisms associated with the TCP protocol with the goal of providing better support for short-lived interactions associated with many widely used TCP-based applications. Current implementations of TCP use a feedback mechanism to adjust the rate at which a machine attempts to send new messages in response to detected losses of data. This mechanism has been highly tuned to handle large data transfers efficiently.

Current applications of the Internet, however, involve many small data transfers such as those associated with small email messages and images used as icons within web pages. TCPs current implementation handles such transfers poorly. So little data is sent that the information collected cannot provide a statistically significant prediction of the network’s capacity. In addition, while the overhead required by TCP is small when amortized over a long data transfer, it represents a significant performance penalty in the context of short data transfers.

This year, with the assistance of Teodora Ivanova ‘03, Professor Murtagh began a project designed to evaluate the relative performance of several schemes for handling clusters of short data transfers associated with web page retrieval. They constructed software to simulate the handling of web requests using serial HTTP request, parallel requests, persistent HTTP and TTCP. This summer, the software will be completed and used in continuing work to collect data on the performance of these techniques.

Professor Murtagh discussed this work on congestion control in a series of lectures entitled “Internet Congestion Control” sponsored by the Williams College Sigma Xi Club in the fall. He attended the ACM SIGCOMM conference on Applications, Technologies, Architectures and Protocols for Computer Communications in August, and the Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies in April.

Assistant Professor James Teresco continued his research on parallel and distributed computing, specifically in the area of dynamic load balancing for adaptive scientific computation. Parallel computation is a well-established and essential tool for large-scale scientific computing. Adaptive approaches, such as the automatic refinement and coarsening of meshes or the variation of method order, often necessitate linked structures that must be explicitly partitioned into sub-domains that can be distributed among processors, assigning equal work to each while minimizing communication. A balanced workload, achieved by a static partitioner, will cease to remain so under adaptive refinement, and will require redistribution during the solution process using a dynamic load balancing procedure.

Professor Teresco is working with Sandia National Laboratories on the development of Zoltan, a software library that provides a common interface to a number of state-of-the-art partitioning and dynamic load balancing algorithms. He traveled to Albuquerque, New Mexico, to meet with the Zoltan group. Professor Teresco’s work on Zoltan is in collaboration with Paul Campbell (Rensselaer and IBM), Karen Devine (Sandia), Joseph Flaherty (Rensselaer), Jamal Faik (Rensselaer), and Luis Gervasio (Rensselaer). They incorporated into Zoltan an octree load balancing procedure that uses an octree structure to cover a computational domain, dividing the work spatially among “terminal octants” (leaf nodes of the tree). A tree traversal is used to divide the octants among partitions to be distributed on a parallel computer.

Recent work includes the use of space-filling curves to linearize the terminal octants in a way such that the quality of the resulting partitions, and in turn, the efficiency of the computation, is improved.

Modern parallel processing is being performed on everything from the largest tightly coupled supercomputers to clusters of workstations. Any adaptive strategy seeking optimal performance must account for processor, memory, and communications hierarchy and heterogeneity. Hierarchical and heterogeneous systems are increasingly common, and present new challenges for the development of efficient software, particularly influencing dynamic load balancing procedures. Professor Teresco continues to work with Devine, Faik, Flaherty, and Gervasio, to support architecture-aware load balancing in Zoltan. Current work includes the automatic construction of a machine model that represents the computational domain, and on algorithms that use this model to guide load balancing. The machine model is based on one developed by Professor Teresco as part of his Ph.D. dissertation. He and Flaherty were awarded a grant entitled “Hierarchical Dynamic Data Management and Load Balancing for Parallel Adaptive Computation,” to support this research. The work is funded by Sandia National Laboratories.

Professor Teresco worked with Lida Ungar ‘02 during the summer of 2002 to analyze the performance of the dynamic load balancing procedures in Zoltan when applied to a number of problems of interest. Ungar also modified the Zoltan implementation of the recursive coordinate bisection algorithm to provide a “slice” partitioning, designed to minimize the number of neighbors with which each processor must communicate. These results were presented at this conference in Barcelona, Spain, in April 2003.

Professor Teresco supervised the senior honors thesis of Joshua Ain ‘03. Ain developed and tested techniques to optimize cache utilization in the presence of “read once” memory accesses. Such access patterns can occur, for example, during a message passing operation in a scientific computation, or when processing audio or video files. Read once memory accesses do not have temporal locality, but will still use cache lines, likely evicting other data from the cache that does have some temporal locality. Using memory access traces obtained from Brigham Young University, Ain simulated the behavior of caches of various types and sizes in the presence of these read once accesses. His theoretical hardware improvement called “NoTime” provided significant improvement in average memory access times by forcing read once memory accesses to use only a single cache line.

Professor Teresco has installed, configured, and continues to maintain a 25-processor Sun Microsystems compute cluster that supports research in parallel and distributed computing in the Computer Science Department. The cluster consists of nine Enterprise servers, connected by fast Ethernet and by a gigabit interconnect from Dolphin. This year, the cluster was expanded to include four Sun Ultra 10 workstations that have allowed more extensive studies of “system-sensitive” computing. In addition to supporting the research described above, the cluster was also used in CSCI 432, Operating Systems, during fall 2002 for a project to study multithreading, and was used extensively by students in CSCI 338, Parallel Processing, during spring 2003.