COMPUTER SCIENCE

For more than two decades, the Department of Computer Science has enjoyed the teaching and research contributions of many faculty, but first on any list would be Kim Bruce. Kim was both instrumental in establishing an independent department and in drawing faculty who would shape an innovative curriculum and a strong program of research. In 2005, as we shall see below, Kim was rewarded for his efforts not once, but twice: first, with national recognition as a computer science educator, and second with a post at his alma mater, Pomona College, in sunny California. While Kim and his family will be missed as they leave Williamstown, the department looks forward to a fall of refining excuses for winter visits to Claremont where, as Barron’s puts it, “Sun filled skies all year and proximity to the Pacific Rim give Pomona students (and faculty) an educational atmosphere not found elsewhere.” Kim: thank you and keep the light on.

Robot maneuvers through a maze in Prof. Murtagh’s Winter Study course.

January–a month of cold weather and big storms–brought a number of students into a month long Lego robotics course in the toasty “very special purpose” room in our unix lab. Tom Murtagh and a dozen students designed and built a wide variety of robots to solve a number of problems. The one on the right, for example, was prepared for a competition that required searching for a candle in a maze and extinguishing its flame. (No fire alarms were triggered.) Some of the experiments of this winter study course will likely appear in Tom’s new introductory course, available beginning fall 2005.

Each week colloquium speakers visit the department and discuss research with interested students and faculty. Through the generosity of the Class of 1960, the department augments its colloquium series with talks by a contributor in computer science, once each semester. This year Mike Burrows (of Google) and Michael Reed (of Blue Sky Studios) visited the department, spoke with students and faculty, and gave especially wonderful talks. As part of the Class of 1960 scholars program, several students were invited to special events with the speakers. This year’s scholars were:

The Department is pleased to announce that Professors Bruce, Danyluk and Murtagh completed work on their new introductory textbook, Java: An Eventful Approach, which will be published by Prentice-Hall in July 2005. This work was partially 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.

Stacia Wyman visited us this year from the University of Texas where she earned her degree working with computer scientists and biologists reconstructing phylogenic relationships by analyzing gene order data. During the year, Stacia has challenged students in both theory (CSCI 361) and practice (CSCI 256). This summer, Neal Holtschulte ’06, is working with Stacia, developing web support for their analysis tools at the University of Texas. We are fortunate to have Stacia’s help this coming year, a year we assume will be modeled after the last: an ongoing serious conversation about education, research, and automobile repair, with an undertow of teary-eyed laughter.

Professor Kim Bruce spent the 2004-2005 academic year at the University of California at Santa Cruz. He divided his time there between doing research in computer science and taking classes and starting research in linguistics, especially the semantics of natural languages. His work in linguistics was supported by a grant from the Mellon Foundation.

His work in Computer Science continued to focus on the design of type systems that offer added expressiveness in object-oriented languages. He is particularly interested in supporting simultaneous specialization in mutually recursive classes and providing module systems that provide support for information hiding, yet provide sufficient hooks to allow later specialization.

Bruce presented several talks on his programming languages research including invited keynote lectures at conferences in Leiden, the Netherlands in November 2004, and in Long Beach in January 2005. He will give a tutorial on the Foundations of Object-Oriented Languages at OOPSLA 2005 in San Diego, CA, in October. The tutorials are based on material in his text, Foundations of Object-Oriented Languages: Type and Semantics, published in 2002 by MIT Press. Prentice Hall of India published a new version of this text to be distributed in South Asia.

Bruce's new research in the semantics of natural languages draws together his earlier research in mathematical logic and in programming languages semantics. The research he is pursuing with Professor Donka Farkas and James Isaacs of the University of California at Santa Cruz involves modeling multi-agent discourse to support a variety of speech acts that take place in a cooperative dialog between speakers.

Professor Bruce was presented the 2005 ACM SIGCSE award for outstanding contributions to Computer Science Education. As a consequence, he was invited to present the keynote talk at the SIGCSE 2005 Conference on Computer Science Education in St. Louis, MO. At the same meeting, he participated in a panel on the use of tools to teach objects early in introductory courses. He presented 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, in June 2004. Murtagh presented a similar talk at SIGCSE. Bruce presented a workshop on the materials from their forthcoming book at OOPSLA ’04 in Vancouver, B.C. in October.

Bruce is a co-organizer of the ECOOP 2005 Ninth Workshop on Pedagogies and Tools for Learning Object-Oriented Concepts in Glasgow, Scotland, in July 2005. Bruce also continued his service on the 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) and developing libraries to make it easier to teach Java to novices. He has continued to be an active participant in the e-mail list supporting high school teachers for the Advanced Placement CS exam.

Seduced by the California weather and the lure of new challenges, Bruce has decided to accept a new position as the Reuben C. and Eleanor Winslow Professor Computer Science at Pomona College in Claremont, CA, starting July 1, 2005. His goal is to help Pomona build a Computer Science Department equal in quality to that of Williams. He leaves with some regret, having spent the last 28 years at Williams, enjoying the stimulation of his colleagues and students.

In the fall, Professor Andrea Danyluk taught two courses: Theory of Computation and Artificial Intelligence: Image and Reality. The latter is an introductory course intended primarily for non-majors. Prof. Danyluk substantially revised this course, which was last taught in 2001. Among other things, she added two new week-long lecture topics – computer vision and natural language processing. She also modified the lab component of the course. In labs, students build and program simple vehicular robots. The robotic vehicles are built around the Handy Board, a processor for running robotic applications that was developed at the MIT Media Lab. This year a number of labs involved the use of simple sonar devices to assist in navigation and obstacle detection. Students also built grippers that enabled the robots to lift and move lightweight obstacles. We were fortunate to have Fred Martin give a colloquium in the fall. Fred Martin, currently a faculty member at the University of Massachusetts, Lowell, is the developer of the Handy Board.

In the spring semester, Prof. Danyluk enjoyed a sabbatical leave. During her leave, she worked with Prof. Carla Brodley at Tufts University. Prof. Danyluk’s research is in artificial intelligence, specifically in machine learning. Her focus has been on inductive concept learning and its application to real-world problems.

Inductive concept learning algorithms extrapolate patterns from large data sets. For example, say that we have a database of information about patients who have been diagnosed with disease D, and say that this database tracks patients for up to 10 years after initial diagnosis. Furthermore, say that we are interested in finding a general rule that will help predict which future patients will have a recurrence and which will not. By analyzing the recurrence data in the original database using an inductive concept learning algorithm, it might be possible to find such a useful general pattern.

This spring Prof. Danyluk has been particularly interested in data that involve sequences of events over time – a computer user’s mouse movements, a truck driver’s driving behavior (use of the accelerator and brake, etc.), a series of alarms generated by a network monitoring device. More specifically, she is considering the question of being able to distinguish between “normal” sequences of events and anomalous sequences. For example, is it possible to develop a program to track a computer user’s actions (in terms of keyboard usage, mouse movements, etc.) and automatically develop a model of that user? Can that model then be used identify another user masquerading as the first? There are many interesting and practical applications where such anomaly detection is critical.

This year two students worked with Prof. Danyluk on research. During the Winter Study Period, Alexandra Constantin ‘07 investigated the possibility of applying Hidden Markov Models to the user authentication problem described above. Marina (Masha) Lifshin ’05 completed an honors thesis on the topic of artificially intelligent animation generation.

Prof. Danyluk served on the program committee for ICML 2005 (the International Conference on Machine Learning), which will take place in Bonn, Germany in July. She was also a member of the program committee for a Special Track on AI Education, held in conjunction with FLAIRS, the Florida AI Research Symposium. She has also served as a reviewer for the Journal of Machine Learning Research) and the Journal of Artificial Intelligence Research.

Professor Stephen Freund's research for the past year has continued to focus on verifying properties of concurrent programs with light-weight analysis tools. The properties of interest include atomicity. A routine is ‘atomic’ if its execution is not affected by and does not interfere with concurrently-executing threads. Atomic routines are easy to reason about because their behavior in a multithreaded context is the same as their behavior in a sequential context. Freund and his colleagues had previously designed a number of static and dynamic analysis techniques for checking whether specific routines are atomic.

One shortcoming of these techniques is that they do not properly handle a number of programming idioms in which methods are intuitively atomic, but irreducible by our analysis. With Cormac Flanagan and Shaz Qadeer (Microsoft Research), Freund investigated ways in which an atomicity analysis could better handle these irreducible blocks that cause spurious warnings. The results were published in the Proceedings of the ACM International Symposium on Software Testing and Analysis, and received the ACM SIGSOFT Distinguished Paper Award.

Freund also developed a type inference engine for identifying race conditions, and designed an inference algorithm with Cormac Flanagan and Masha Lifshin ‘05 that automatically determines which methods in a program are atomic (and therefore free from potentially bad interference).

Professor Bill Lenhart finished his 18-month term as Acting Dean of the Faculty this past January. He was delighted to return to the department this spring to teach CSCI 371, an upper-level elective in computer graphics. He is now beginning an eagerly awaited sabbatical during which he plans to pursue both his long-standing interests in the design and analysis of algorithms in graph theory and computational geometry, as well as his more recent interests in quantum computation and complexity theory.

Professor Tom Murtagh received a grant of $60,186 from the NSF CCLI program. The project supported by the grant, “Providing Breadth while Retaining Depth and Focus in an Introductory Computer Science Course,” aims to develop a replacement for traditional introductory computer science courses. Most introductory computer science courses focus on teaching basic programming skills. Currently, the only widely recognized alternative to focusing on programming skills in an introductory CS course is to teach what is called a “breadth-first” introductory course. These courses present brief treatments of an array of topics that typically includes hardware organization, operating systems, algorithm analysis, artificial intelligence, programming languages, etc. While such courses can present much interesting material, they lack coherence. Murtagh’s goal is to implement an introductory computer science course that uses one area of specialization as a vehicle to present a broad overview of the techniques and principles underlying all work in computer science. In a sense, the course will be “depth-first.” Rather than surveying a broad range of topics, it will examine a single subfield within our discipline, computer networking, in as much depth as possible in an introductory course. In another sense, the course will be “breadth-first.” The material presented to students will be designed to illustrate techniques and principles of broad applicability within our discipline. During the summer of 2005, Brendan Dougherty ‘06 worked with Murtagh to develop materials for this project. Together with Stacia Wyman, Murtagh will offer the first course based on these ideas in fall 2005.

Murtagh attended the SIGCSE 2005 Technical Symposium on Computer Science Education in February where he presented a paper “Why structural recursion should be taught before arrays in CS 1” co-authored with Kim Bruce and Andrea Danyluk. He also attended the Second USENIX Symposium on Networked Systems Design and Implementation.

Professor James Teresco returned to active teaching duty following his year in Albuquerque, New Mexico, as a visiting researcher at the Computer Science Research Institute at Sandia National Laboratories. He continued his research on parallel and distributed computing, specifically in the area of dynamic load balancing for adaptive scientific computation

Modern parallel processing is being performed on everything from the largest tightly-coupled supercomputers to clusters of workstations in the transient and dynamic environments more recently 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. Teresco continued his 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 <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.

Teresco’s team is developing the Dynamic Resource Utilization Model (DRUM) <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 in part by Sandia National Laboratories.

Teresco worked with Laura Effinger-Dean ’06 and Arjun Sharma ’07 on the DRUM project during summer 2004. Effinger-Dean’s work involved an extension to DRUM that allow it to be used in conjunction with the Network Weather Service cluster monitoring toolkit. Sharma developed a new version of DRUM’s graphical configuration tool, which he named DRUMHead. These successful projects were the subject of the paper that Teresco presented at the 5^th International Conference on Computational Science in May 2005, in Atlanta.

DRUM’s capability to support computation in heterogeneous environments was the focus of a section Teresco’s group contributed to an article in Applied Numerical Mathematics. DRUM and hierarchical partitioning were the focus of an article that appeared in Computing in Science & Engineering. Teresco presented the hierarchical partitioning work at the PARA’04 Workshop on State-of-the-Art in Scientific Computing in Copenhagen in June 2004, and wrote a paper that has been accepted for publication in the conference proceedings. Teresco also spoke about DRUM at the 2004 SIAM Annual Meeting in Portland, Oregon, in July 2004, and in two talks at Williams. The first, part of the department’s colloquium series, was given in October 2004. The second was delivered as a Science Lunch talk in November. Finally, Teresco presented work on dynamic load balancing tools, including DRUM, that support parallel execution of discontinuous Galerkin methods at the Third M.I.T. Conference on Computational Fluid and Solid Mechanics in June 2005 in Cambridge.

Teresco, Devine and Flaherty co-authored a chapter that has been accepted for inclusion in the book Numerical Solution of Partial Differential Equations on Parallel Computers. This thorough review of modern issues in partitioning and dynamic load balancing will be an important resource for those whose work requires partitioning and dynamic load balancing, but who do not have the time or expertise to search through the literature to find the appropriate algorithms and software to do their work.

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 MPI/IOS, a middleware system that allowed existing applications, written using the popular Message Passing Interface (MPI), to take advantage of transient and or unreliable computing resources with minimal modification. This work is described in a chapter in the volume Grid Computing: New Frontiers of High Performance Computing.

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

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. This year, Teresco and his co-organizers edited the proceedings of the conference, which appeared as a special issue of Applied Numerical Mathematics in February 2005. The conference was supported by grants from the U.S. Army Research Office and the National Science Foundation. See <www.cs.williams.edu/adapt03/>.

Teresco and 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 Teresco. This year, he edited an article, with contributions by all mini-symposium participants, summarizing the work presented at the mini-symposium for publication in the conference proceedings. See <www.siam.org/meetings/pp04/>.

Teresco and Faik (Rensselaer) co-organized a mini-symposium “Resource-Aware Parallel Computing” at the SIAM Conference on Computational Science & Engineering (CSE05) in Orlando in February 2005 as a follow-up of the successful mini-symposium a year earlier in San Francisco. See <www.siam.org/meetings/CSE05>.

Teresco and Professor David Hemmendinger (Union College) served as co-chairs for student posters at the Tenth Annual Consortium for Computing Sciences in Colleges Northeastern Conference (CCSCNE 2005), held at Providence College in April 2005. See <www.ccscne.org/2005/>.

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

During summer 2005, Teresco will also be developing a new version of his Parallel Processing course to be offered in a tutorial format for the first time in spring 2006.

Duane Bailey steps down as chair this year, handing the baton to Andrea Danyluk, with best wishes and a tip of the hat.

Computer Science Faculty, Williams College

“Faculty Research in Computer Science”
Professor James Teresco, Williams College

“Parallel Adaptive Scientific Computation in Heterogeneous Computing Environments”
Professor Fred G. Martin, University of Massachusetts at Lowell

“Engaging Computing: Makin' It Real for Kids and Undergrads”
Mike Burrows, Google™, Class of 1960 Scholars Program

“Searching the Web: A Behind-the-scenes Look”

“Searching the Web: Technical Challenges and Solutions”
Alumni Panel: Todd Gamblin `02, Art Munson `01, Shimon Rura `03, Evan Sandhaus `02, Davis Stevenson `04, and Evan Gee `04

“Careers in Computer Science”
Jennifer Neville, University of Massachusetts at Amherst

“Knowledge Discovery with Relational Dependency Networks”
Professor Wes Huang, Rensselaer Polytechnic Institute

“Robotic Mapping and Exploration with Sensing-Limited Robots”
Professor Daniel Bilar, Colby College

“QRAN- Quantifying and Managing Software Risk in Computer Networks”
Professor Tia Newhall, Swarthmore College

“NSWAP: A Network Swapping System for Linux Clusters”
Professor Michael Rosenstein, University of Massachusetts at Amherst

“Human Interaction with Robots: From Tools to Partners”
Professor Gleb Naumovich, Brooklyn Polytechnic University

“Obfuscation of Design Intent in Object-Oriented Applications”
Brent Heeringa, University of Massachusetts at Amherst

“An O(In(n))-Approximation for Decision Trees”
Professor Carlos Varela, Rensselaer Polytechnic Institute

“Toward a World-Wide Computer: Software Technology for Computational Grids”
Dr. Roddy Collins, GE Global Research

“Recognition of Science Content Using Region-Based Classification”
Dr. Perry Cheng, IBM, T. J. Watson

“The Metronome: Real-time Garbage Collection”
Dr. Michael Reed, Blue Sky Studios, Class of 1960 Scholars Program

“Computational Aspects of Feature Animation”

“Lead Character Modeling for Feature Animation”
Professor Camille C. Price, Stephen F. Austin State University

“Cascaded Boltzmann Machine for Partitioning and Mapping Software”
Jamal Faik, Rensselaer Polytechnic Institute

“A Model for Dynamic Load Balancing on Heterogeneous Clusters”
Professor David Goldschmidt, Rensselaer Polytechnic Institute

“A Comparison of Keyword-Based and Semantics-Based Searching”

Laura Effinger-Dean `06, Sharma Arjun `06, Christopher Douglas `05, Charles Giammattei `05, James Kingsbery, Jr. `06

“What I Did This Summer: Part I”
Marina Lifshin `05, Ashok Pillai `05, Brian Hirshman `06

“What I Did This Summer: Part II”
Marina Lifshin `05

“Artificially Intelligent Animation Generation”
Alexandra Constantin `06

“Hidden Markov Models in the Analysis of Time Series Data”
Marina Lifshin `05, Senior Thesis Defense

“Artificially Intelligent Animation Generation”

Kim B. Bruce

“Events and Objects First: An Innovative Approach to Teaching Java in CS 1”
OOPSLA 2004, Vancouver, B.C., October 2004

“Fixing the Meaning of Object-oriented Languages,”
Formal Methods for Components and Objects, Leiden, the Netherlands, November 2004

“Object-oriented Languages, Fixed Points, and Systems of Classes”
International Workshop on Foundations of Object-Oriented Languages, Long Beach, CA, January 2005

“Using Abstractions to Make Concepts Concrete,”
SIGCSE 2005, St. Louis, MO, February 2005.

“Objects-Early Tools – A Demonstration”
SIGCSE 2005, St. Louis, MO, February 2005

“Resolved: Objects Early Has Failed,”
SIGCSE 2005, St. Louis, MO, February 2005

Three seminar presentations, Computer Science Department, University of California, Santa Cruz
Stephen Freund

“Type Inference for Atomicity”
ACM Workshop on Types in Language Design and Implementation, Los Angeles, CA, January 2005

“Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs”
University of Illinois, Urbana-Champaign, IL, August 2004

“Exploiting Purity for Atomicity”
International Symposium on Software Testing and Analysis, Boston, MA, July 2004

“Type Inference Against Races”
Static Analysis Symposium, Verona, Italy, August 2004
James Teresco

“Hierarchical Partitioning and Dynamic Load Balancing for Scientific Computation”
PARA 04 Workshop on State-of-the-Art in Scientific Computing, Copenhagen, Denmark, June 2004

“Dynamic Load Balancing for Heterogeneous and Hierarchical Clusters”
2004 SIAM Annual Meeting, Portland, Oregon, July 2004

“An Overview of Resource-Aware Parallel Computation – with an Emphasis on Hierarchical Partitioning and Dynamic Load Balancing”
SIAM Conference on Computational Science & Engineering, Orlando, February 2005

“Resource-Aware Parallel Computation for Clusters”
International Conference on Computational Science 2005: ICCS ’05, Atlanta, May 2005

“Dynamic Load Balancing for Heterogeneous and Hierarchical Computing Environments”
Third M.I.T. Conference on Computational Fluid and Solid Mechanics, Cambridge, June 2005