COMPUTER SCIENCE DEPARTMENT

To choose a life of teaching and research at the undergraduate level is to constantly surround oneself with youth. This year, the department of computer science graduates a class of 14 young and multitalented majors. Over the years, many of these students have performed research with faculty, several have second majors, and one is the class valedictorian.

In addition, the department has been host to the youthfully energetic Brent Heeringa whose enthusiasm for teaching has rubbed off on both students and faculty alike. Brent returns to the University of Massachusetts to finish his doctorate—and we look forward to following his promising career in computer science!

The department launched efforts to introduce changes to the computer science curriculum to be introduced in fall 2005. These changes will allow non-majors to enjoy a broader view of computer science, and will introduce new courses to help solidify both practical and theoretical skills of in computer science.

Through the generosity of the Class of 1960 Scholars program, the department invited two important contributors in computer science – Rebecca Mercuri, an expert on electric voting technologies and Manuela Veloso, an expert on artificial intelligence and robotics and a founder of the RoboCup competitions for robotic soccer players. As part of this program, fifteen students were selected to be this year’s Class of 1960 Scholars student scholars and meet with the speakers.

The faculty continues its history of strong contributions in research and the landing of several grants. Behind most of the projects discussed below are students whose participation is vitally important to the success of the respective projects.

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 grant from the NSF CCLI program. This approach uses Java as the programming language, and places a heavy emphasis on the use of object-oriented graphics classes, 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. Ashok Pillai ’05 worked with the faculty on software for the course in the summer of 2003, and Brendan Dougherty ’06 will continue that work in the summer of 2004. The final manuscript will be submitted to Prentice-Hall by the end of June, and supporting instructor’s materials will be developed by the end of the summer.

Professor Duane Bailey is in the process of developing a new course, Life as an Algorithm, to be taught beginning spring 2005. The course investigates ideas common to computer science and biology and, while it encompasses many features of the current revolution in biotechnology, it also reconsiders many early papers in computer science and biology that have had an impact on the development of both fields. A draft of this course was offered during winter 2004. Students of the winter study course were hosted by several Williams alumni at MIT’s Broad Institute. Life as an Algorithm will be offered as CSCI 106 (cross-listed in Biology), and will serve as an introductory course in the Bioinformatics, Genomics, and Proteomics Program.

Professor Bailey worked with two senior research students this year, Kai Chen and Christopher Cyll. Bailey’s work with Kai Chen investigated models for DNA computation. This paradigm of computation uses DNA as a carrier of information in a computation that is promoted by complementary pairing and novel uses of existing wet-lab techniques. Most demonstrations of DNA computation involve solving difficult problems of computer science or mathematics. Chen investigated computations that support questions of biology, including string matching and homology. Such methods might provide techniques to perform suspect database searches in the test-tube or to answer phylogenic questions.

Christopher Cyll worked with Bailey to investigate the effect of dynamic memory allocation on cache performance. Cyll developed software to capture the allocation patterns for analysis off-line. Since allocated data may be positioned in a manner that may force the cache to displace useful data, Cyll constructed several placement algorithms that attempt to reduce the number of conflict misses. Cyll was able to identify several techniques that potentially improve the performance of programs that are run using alternative allocation strategies.

Seven students in Bailey’s course on VLSI design and modern architectures generated two different designs for an 8-lap, three-mode stopwatch. Fabricated at current feature sizes, these watch chips are less than two millimeters on a side.

Bailey continues to serve as a reader on the national committees for the Goldwater Science Scholarship, which rewards the top 300 undergraduate scientists in the country, and the Jack Kent Cooke Fellowship, which supports needy, but promising students from middle school through graduate school. He also evaluates curricular proposals for the National Science Foundation.

Professor Kim Bruce continued his research on the type theory and semantics of object-oriented languages. The overall goal of his research continues to be to increase the understanding of the key concepts of object-orientation in order to promote the design of more secure and expressive languages. His research is supported by grants from the National Science Foundation.

Research continued on two 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, after completing his honors thesis, worked as a research assistant during the summer of 2003. 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. Alexandra Constantin ’07 will be continuing this work as a research assistant during the summer of 2004.

Bruce and John “Nate” Foster ’01 wrote a paper based on Nate’s thesis (and the earlier thesis by Jon Burstein) on the design and implementation of the language LOOJ, as well as some more recent work on proving the correctness of the language design. The paper was accepted at ECOOP 2004 in Oslo, Norway. Foster, who was awarded an NSF Graduate Fellowship this spring to support his computer science graduate work at the University of Pennsylvania, presented this paper at ECOOP in June 2004.

The second project involved further work on providing type systems that support simultaneous extension of mutually referential systems of interfaces and classes. This work built on research undertaken earlier with Joe Vanderwaart ’98. 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.

Bruce was a co-organizer of the ECOOP 2003 Seventh Workshop on Pedagogies and Tools for Learning Object-Oriented Concepts in Germany in July 2003. While Bruce is no longer a co-organizer of the workshop, he will present a paper, coauthored with Danyluk and Murtagh, on why structural recursion should be taught early in the first course at the Eighth workshop at ECOOP 2004 in Oslo, Norway, June 2004. The three of them also presented workshops on the materials from their forthcoming book at SIGCSE 2004 in February in Norfolk, Virginia, and at NESCC in April at Union College. Bruce will present another workshop on the same materials at OOPSLA 2004 in Vancouver, B.C. in October.

Bruce chaired the winter meeting of the Liberal Arts Computer Science Consortium at SIGCSE 2004, and chaired a panel there on the newly revised Liberal Arts Computer Science Curriculum, which should be finalized by the end of the summer of 2004. Bruce also served on a newly formed ACM Java Task Force, which has been charged with identifying libraries that can be used to make it easier to teach Java to novices (e.g., students taking intro courses). Portions of the objectdraw library developed with Danyluk and Murtagh have been submitted to this task force for their consideration. Bruce has also been an active participant in the e-mail list supporting teachers for the Advanced Placement Computer Science exam. He was invited to address the graders of the Advanced Placement Computer Science exam on issues in teaching Java in introductory computer science courses, but was unable to accept because the timing conflicted with the ECOOP 2004 meeting.

Bruce participated in a panel on “Mathematical Logic in Computer Science Education” at the annual meeting of the Association for Symbolic Logic in Pittsburgh in May 2004. He also co-authored a paper on the role of mathematics in computer science that was published in the Communications of ACM in September 2003.

Bruce was involved in several other activities through the last academic year. He served as outside evaluator in a promotion case this fall. He served on a visiting committee for Mathematics and Computer Science at Skidmore College in November 2003. He attended the POPL 2004 and FOOL 10 meetings in Venice, Italy, in January 2004, the IBM Programming Days Workshop in May 2004, and the ECOOP 2004 meeting in Oslo, Norway, in June 2004. He served on the program committee for the FOOL 10 and IBM Programming Languages Day workshops, and chaired sessions at both.

His most exotic trip was to give an invited keynote address at the Andrei Ershov Fifth International Conference, Perspectives of System Informatics, in Novosibirsk, Siberia, Russia, in July 2003, where he was also interviewed on a local TV station. Later that month he gave a talk at the University of Genoa, in Genoa, Italy, and then participated on an informal panel on the future of object-oriented languages at the workshop on Object-Oriented Language Engineering for the Post-Java Era at ECOOP 2003.

He gave an invited talk at the International LISP conference in New York City. He gave talks at the New England Programming Languages Seminar at Northeastern University in February 2004 and at Boston University in April 2004. Finally, he gave tutorials on the Foundations of Object-Oriented Languages at OOPSLA 2003 in Anaheim, CA, and at ECOOP 2004 in Oslo, Norway. The tutorials are based on material in his text, Foundations of Object-Oriented Languages: Type and Semantics, published in 2002 by MIT Press.

On campus, he served as a member of the Committee of Appointments and Promotions, as a member of the Linguistics Advisory Committee, and as an advisor of first year students and computer science majors. He also made a presentation to an alumni group on the uses of technology in classes at Williams.

Bruce will be on leave during the 2004-2005 academic year as a visiting professor at the University of California at Santa Cruz. The leave will be partly financed by a Mellon Renewal Fellowship awarded by Williams. The grant will support his study of natural language linguistics, a new area for him. He will also be continuing his research on the design of object-oriented languages.

Professor Andrea Danyluk’s research is in the field of artificial intelligence (AI), specifically Machine Learning. Her research focus is on the application of inductive machine learning algorithms. Inductive learning algorithms extrapolate general rules or trends from large data sets. One might consider applying such algorithms to a phone company’s database of network outages, for instance, to determine general rules that might predict the occurrence of such events before they actually happen. Professor Danyluk enjoyed a semester of sabbatical in the fall of 2002, during which she was able to focus much of her time on her research.

In March, Professor Danyluk gave a talk entitled “Robotics as a Motivator in an AI Course for Non-majors” at a Symposium on Accessible Hands-on Artificial Intelligence and Robotics Education. A paper with the same title appears in the working notes from the symposium, which is available as a Technical Report from AAAI, the American Association for Artificial Intelligence. The course described in the paper is Artificial Intelligence: Image and Reality (CSCI 108). Professor Danyluk is working this summer to revise this course for the fall semester. This revision will include new laboratory exercises with some exciting new additions to our collection of robots.

In the spring, Professor Danyluk taught Artificial Intelligence. This offering of the course included a new unit on Bayesian Networks and probabilistic reasoning as well as an expanded unit on robotics.

This year Professor Danyluk served on the Advisory Board and Program Committee for the International Conference on Machine Learning. She was also a member of the program committee for a Special Track on AI Education, held in conjunction with FLAIRS-04, the Florida AI Research Symposium. She will serve as a member of that committee next year as well. In the fall, she served as a reviewer for FIPSE, the Fund for the Improvement of Postsecondary Education.

Professor Stephen Freund continued his work on program analysis tools for identifying concurrency errors in multithreaded programs. The primary focus for the last year has been on tools to find atomicity errors. Atomicity is a strong but widely used noninterference property that excludes unintended interactions between threads. This work is supported by a $636,000 grant from the NSF/NASA HDCCSR program, which was awarded to Freund, in collaboration with Cormac Flanagan and Martin Abadi at University of California, Santa Cruz. Marina Lifshin ’05 is spending the summer extending a static atomicity checker to infer atomicity specifications.

Freund collaborated with Shaz Qadeer at Microsoft Research on a paper which developed a new technique for checking whether the implementation of a multithreaded program conforms to its specification. This work was presented at the Formal Techniques for Java-like Programs Workshop in Darmstadt, Germany, and it is published in the Journal of Object Technology.

Together with Flanagan, he also developed a dynamic atomicity checker that monitors a program for errors as it executes. The paper on this tool was presented at the Symposium on Principles of Programming Languages in Venice, Italy.

Freund, with John Mitchell at Stanford University, published a paper in the Journal of Automated Reasoning that summarizes his thesis work on formally specifying the Java byte code verifier, which is the part of the Java virtual machine that prevents untrusted code from compromising system security by performing illegal operations.

In addition to presenting the papers listed above at workshops and conferences, Freund gave technical talks on his research at Stanford University, Berkeley, AT&T Research, University of Pennsylvania, the New England Programming Languages Seminar, and Microsoft Research.

Brent Heeringa, along with Micah Adler (Assistant Professor, University of Massachusetts, Amherst) have a paper on optimal website design at the 31st annual International Colloquium on Automata, Languages and Programming in Turku, Finland in July. The conference is considered by many to be the top European venue for theoretical computer science. Brent will also present the work at the conference. In addition, Heeringa aided Professor Adler during the final program committee meeting of the Symposium on Parallel Algorithms and Architectures.

Professor William Lenhart began his term as Acting Dean of Faculty in the fall, and still found time to advise two students – Brent Yorgey and Tom White – on graphics-related research projects! Lenhart’s administrative term ends after fall 2004, when he hopes to take a well-deserved leave. We look forward to his return to the department, and join the rest of the college in thanking him for his hard work these past months.

Professor Barbara Lerner continued her research into the coordination of human and automated agents. The recent focus of her work has been to use software verification tools to analyze coordination processes written in the language Little-JIL. During summer 2003, two students participated in this research. Shimon Rura ’03 worked on a tool to assist an analyst in translating Little-JIL processes into FSP models to be analyzed by the LTSA model checker. Model checkers require a finite model of a process to operate, but processes typically include features such as looping and recursion that express unbounded execution. A straightforward translation of Little-JIL to FSP thus results in an infinite model. The translation tool assists an analyst in identifying portions of the process where unbounded behavior exists and redefining those portions to be a finite approximation of the original process so that it can be model checked. Once translated into FSP, we are able to prove whether or not a process contains deadlock and whether or not it satisfies safety properties of interest to the analyst.

Topher Cyll ’04 explored the application of Bogor, another model checker, to the analysis of Little-JIL processes. The unique characteristic of Bogor is that it is an extensible model checker. Bogor provides the general mechanisms to perform model checking and also provides hooks to allow a language’s semantics to be defined within the model checker. One of the major drawbacks of model checking is state space explosion, which dramatically limits the size of programs that can be checked. By building a language-specific model checker using Bogor, we expect to be able to analyze larger processes than we can using the translation technique required by LTSA.

Professor Murtagh continues to investigate the behavior of the congestion control mechanisms associated with the TCP protocol. 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 interacts poorly with internet applications that involve many small data transfers such as those associated with small email messages and images used as icons within web pages.

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. Professor Murtagh’s work seeks to develop congestion control mechanisms better suited to such small data transfers. This year, with the assistance of Thomas White ’04, Professor Murtagh continued work on the construction of software to simulate the handling of web requests using serial HTTP request, parallel requests, persistent HTTP and TTCP.

In March, Professor Murtagh attended the First USENIX Symposium on Networked Systems Design and Implementation held in San Francisco, CA.

Professor James Teresco continued his research on parallel and distributed computing, specifically in the area of dynamic load balancing for adaptive scientific computation. He was on leave for 2003-04, and spent much of this productive and enjoyable year in Albuquerque, New Mexico, as a visiting researcher at the Computer Science Research Institute at Sandia National Laboratories. Professor Teresco worked in the computer science and mathematics department at Sandia.

Modern parallel processing is being performed on everything from the largest tightly-coupled supercomputers to clusters of workstations more recently in the transient and dynamic environments found in Internet, or “Grid” computing environments. 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 continued a collaboration with Dr. Karen Devine (Sandia), Professor Joseph Flaherty (Rensselaer), and Rensselaer Ph.D. candidates Jamal Faik and Luis Gervasio, to develop support for architecture-aware load balancing in the Zoltan Toolkit (http://www.cs.sandia.gov/Zoltan/). Zoltan is a software library developed at Sandia that provides a common interface to a number of state-of-the-art partitioning and dynamic load balancing algorithms. Professor Teresco’s team developed the Dynamic Resource Utilization Model (DRUM) (http://www.cs.williams.edu/drum/) to address partitioning and dynamic load balancing on clusters with heterogeneous and hierarchical hardware resources. DRUM includes a model that encapsulates hardware resources and their interconnection topology, and provides monitoring facilities for dynamic evaluation of communication, memory, and processing capabilities. DRUM is also used to guide Zoltan’s hierarchical partitioning and dynamic load balancing procedures, which were implemented by Professor Teresco while at Sandia. Here, different balancing procedures are used in different parts of the domain. This work has been funded by Sandia National Laboratories.

Professor Teresco worked with Diane Bennett ’03 during the summer of 2003 to analyze the performance of the dynamic load balancing procedures in Zoltan when applied to a number of problems of interest. Bennett’s work continued a project from the previous summer by Lida
Ungar ’02.

Professor Teresco is also investigating the efficient execution of parallel adaptive software in dynamic environments, in collaboration with Professor Szymanski (Rensselaer), Professor Varela (Rensselaer), Professor Flaherty (Rensselaer), and Rensselaer Ph.D. candidates Kaoutar El Maghraoui and Travis Desell. As part of this project, the team is developing SALSA-MPI, a middleware system that allowed existing applications to take advantage of transient and or unreliable computing resources.

Professor Teresco has begun a new collaboration with Professor Suvranu De (Rensselaer) and Professor Flaherty (Rensselaer) to investigate digital surgical simulations. Much like flight simulations, computational surgical simulations will eventually be used to train medical students and practitioners, allowing the trainee to touch, feel, and manipulate virtual tissues and organs through the same surgical instrument handles used in actual surgery, while seeing high-quality images of their deformations as in a real surgery. Modeling of the interaction of surgical tools with soft biological tissues requires an update rate of about 1kHz to drive a force feedback device in real time. Professor Teresco and his students will develop software infrastructure to allow numerical procedures to operate in parallel computing environments to provide the real-time feedback needed make such a system a reality.

Professor Teresco continues to be involved in the Bioinformatics, Genomics and Proteomics group at Williams, with his primary interest being high-performance computing issues.

Professor Teresco, with Professor Slimane Adjerid (Virginia Tech) and Professor Peter Moore (Southern Methodist), organized the conference ADAPT 03: Adaptive Methods for Partial Differential Equations and Large-Scale Computation, which was held in Troy, New York, in October 2003. Fifteen invited talks and twenty-one poster presentations were made over two days. The conference was supported by grants from the U.S. Army Research Office and the National Science Foundation. See http://www.cs.williams.edu/adapt03/.

Professor Teresco and Professor Flaherty (Rensselaer) co-organized the mini-symposium “Architecture-Aware Parallel Computing” at the Eleventh SIAM Conference on Parallel Processing for Scientific Computing (PP04), held in San Francisco, California, in February 2004. Seven talks were given by experts in the field, including the introductory and overview talk given by Professor Teresco. He is currently editing an article summarizing the work presented at the mini-symposium for publication in the conference proceedings. See http://www.siam.org/meetings/pp04/.

Professor Teresco and Professor Bailey served as co-chairs for tutorials, workshops, and panels at the Ninth Annual Consortium for Computing Sciences in Colleges Northeastern Conference (CCSCNE 2004), held at Union College in April 2004. See http://www.ccscne.org/2004/.

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 9 Enterprise servers, connected by fast Ethernet and by a gigabit interconnect from Dolphin, plus four Sun Ultra 10 workstations that have been used extensively in the development and testing of DRUM’s heterogeneous processor speed support. In addition to supporting research, the cluster is used in two of Professor Teresco’s upper-level electives (CSCI 432, Operating Systems, and CSCI 338, Parallel Processing). See bullpen.cs.williams.edu.