COMPUTER SCIENCE DEPARTMENT

This was a busy and exciting year for the department. Assistant Professor Andrea Danyluk was granted tenure and will become an Associate Professor on July 1, 2001. We welcomed Assistant Professor Barbara Lerner to our department this past fall, having enticed her away from the University of Massachusetts. Professor Lerner’s area of expertise is Software Engineering. This spring we were delighted to hire our newest faculty member, Assistant Professor James Teresco, who will be finishing his Ph.D. in Computer Science at Rensselaer Polytechnic Institute this summer before joining our department this fall. Professor Teresco specializes in the area of parallel processing. Also visiting us this year from the University of Washington will be former major, Sean Sandys ’95, who was selected by Williams to be a Bolin Fellow. Sean will be on campus teaching and finishing his Ph.D. thesis. The department was also the recipient of a generous gift from Richard Ward ’89, which will be of great help to us as we begin to equip our new home in the recently remodeled Thompson Chemistry building.

The department continued to plan and prepare for our move into the new and expanded space. By the end of the summer, we hope to be completely ensconced in Thompson Chemistry, where we will enjoy not only more extensive laboratory space, but also a new “office suite” on the third floor. We will miss our birch-flavored common area (see above), but it will be replaced by an improved space for student-faculty interaction suited for discussions, lunches, and small talks. Our new laboratories will be equipped with the latest machines: The lab for introductory courses will feature Macintosh G4 computers and the lab for upper division courses includes high-speed Dell workstations running FreeBSD Unix. In addition, there will be a new digital-logic lab supporting our two computer architecture courses. Please come visit our new home!

Over the past two years, the department has been involved in a large-scale redesign of our curriculum. Thanks to generous support from the College, our faculty has been able to devote a significant amount of time to the reorganization and modernization of existing courses and the development of new courses.

A nostalgic portrait of the Computer Science Department in front of the Bronfman ‘Birches’.

The department made significant revisions to its introductory programming course, CSCI 134, during the year. Last summer, three members of the department, Kim Bruce, Andrea Danyluk and Tom Murtagh, devoted considerable effort to the task of planning how to update the course. The previous version of the course used the Pascal programming language. The new version is based on the Java programming language. Making this transition required developing completely new materials for lectures and labs.

In preparation for the course, Professors Kim Bruce, Andrea Danyluk and Tom Murtagh designed a library to provide students with a streamlined interface through which they could access the features of Java that support graphics and the handling of a program's user interface. This library was implemented with the assistance of Jonathan Kallay ’00 and Junghee Yang ’00. The library made it possible to incorporate what would normally be considered advanced topics into the course relatively early in the semester.

The support of the library had a clear impact on the nature of the projects students completed as lab assignments. By the fourth week of the class, student's were already able to complete implementations of “Frogger,” a simple graphical game involving the animation of multiple vehicles and a mouse-based user interfaces. As the semester progressed, students completed labs involving sound generation and network access. The final projects for the both the fall and spring offerings of the course were re-implementations of “classic” video games: Pacman in the fall and Space Invaders in the spring.

In addition to providing the tools needed to enable students to complete projects they would find motivating, the library enabled the instructors to take an approach to the material that had significant pedagogical advantages. Java is an object-oriented language. There is little agreement, however, on how to introduce the object-oriented approach to software construction to beginning programmers. Some consider the object-oriented approach too advanced for a first course. Others believe it should be emphasized from the first day. Even those who wish to emphasize object-oriented concepts from the start, however, find it difficult to accomplish this in the face of the many other basics that must be introduced.

Two features of the library developed for CSCI 134 addressed the problem of how to introduce object-oriented programming. The graphics primitives supported by the library were designed to emphasize the concept of objects. Each entity displayed on the computer screen corresponded to an object within the student's Java program. Invocations of the methods associated with these objects produced immediate, tangible changes on the display. The graphics tools ensured that the students quickly became familiar with the notion of objects and the use of methods to manipulate their states. At the same time, support for event driven programming within the library familiarized students with the mechanisms they would eventually use to define their own classes of objects.

The approach taken in the course was novel in many ways. As mentioned above, the library supported the use of event driven programming. In the course, rather than write programs oriented around a single “main program” and a single thread of control, students viewed their programs as collections of methods designed to respond to user actions. In conjunction with this event-driven style of programming, it was also appropriate to introduce the use of concurrent threads within the first third of the course.

Professors Bruce, Danyluk and Murtagh continue to work on the development of this course. After the initial offering of the course, they wrote a paper describing the course entitled “A Library to Support a Graphics-Based Object-First Approach to Cs1.” Professor Bruce presented this paper at the ECOOP 2000 Workshop on Tools and Environments for Understanding Object-Oriented Concepts in Cannes, France. They have also submitted a grant proposal to the National Science Foundation seeking support to continue the development of material for the course and to distribute them to other institutions.

This year, Associate Professor Duane Bailey returned from leave to continue work on aperiodic structures with Jason Healy. They developed software to determine, given an initial configuration of aperiodic tiles, the empire of its configuration. The empire consists of those tiles whose positions are forced by the completion of a consistent and perfect tiling. Previously, construction of empires was manual and error-prone. The work extends that of Linden Minnick ’98.

This year also marked Professor Bailey’s first offering of the Modern Architecture course. In this tutorial, students analyzed a wide variety of processors, including recent chips from Intel, IBM, Motorola, and Transmeta. Students also designed a 31,000 transistor, 1.2-micron CMOS processor of their own — a silicon version of the WC34000, a virtual machine designed by Professor Murtagh for use in other project courses within the department.

Professor Kim Bruce’s research on the design of statically-typed object-oriented programming languages continued work on extending the expressiveness of object-oriented languages, designing intermediate languages for type-based compilers for object-oriented languages, and writing a monograph on the design 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.

During the summer of 1999, Joe Vanderwaart ’99 once again worked with Professor Bruce on refining the implementation of our object-oriented language, LOOM. This work was an extension of Joe’s thesis on the design of a typed intermediate language for LOOM. The summer work involved crafting and implementing an encoding of objects that would support a more efficient implementation of object-oriented features.

Professor Bruce's main research work during the summer of ’99 and the following academic year was on writing a monograph titled “Foundations of Object-Oriented Languages.” The book is a careful account of research over the last ten years on the types and semantics of class-based object-oriented languages. MIT Press has agreed to publish the monograph, which is expected to appear by the summer of 2001.

Professor Bruce received a new NSF research grant, “RUI: Design of Object-Oriented Programming Languages” to support his research on object-oriented programming languages. The grant provides over $188,913 to support his research over the next three years; this includes funds to hire students as summer research assistants.

Professor Bruce continued as chair of the organizing committee for the 7th International Workshop on Foundations of Object-Oriented Languages (FOOL), held this year in Boston in association with the ACM Symposium on Principles of Programming Languages. He also ran the meeting this year when the chair of the program committee was unable to attend. For these efforts he received an ACM Recognition of Service award for the third time. He also completed work as editor of two special issues of Information and Computation that contain the best papers from FOOL 5 and 6, respectively. These issues should be in print sometime this year.

Much of the last year was spent working with Professors Danyluk and Murtagh in redesigning our introductory course, CSCI 134, as described earlier. In June 2000, he presented talks on this work at the Workshop on Tools and Environments for Understanding Object-Oriented Concepts at the European Conference on Object-Oriented Programming in Cannes, France, and at the Liberal Arts Computer Science Consortium meeting at Bowdoin College. In June 2000, Professor Bruce, along with Danyluk and Murtagh, also applied for an NSF CCLI grant to support further development of this course. They intend to further develop the library, prepare on-line materials, and write an introductory text based on the new course.

Professor Bruce also taught CSCI 361, Theory of Computation, and CSCI 334, Principles of Programming Language. As part of the general curriculum revision that is taking place in the department, he changed the CSCI 361 syllabus to include new material on the lambda calculus as a model of computation, and on the Pi calculus as a model of concurrency. He also made several changes to the CSCI 334 syllabus. The material on object-oriented languages was modified to include discussions of GJ, a new extension of Java, rather than Eiffel, and included much more extensive material on typing problems with object-oriented languages. He also dropped all mention of logic programming languages, inserting instead more material on concurrency. The new concurrency material placed more emphasis on Java as an example of a language supporting concurrency. This material included criticism of the standard Java support, comparing this with a Java-based implementation of Hoare’s Communicating Sequential Processes (CSP). This updating of the syllabus should result in a course whose material is more relevant for expected changes and innovations in programming languages over the next several years.

In spite of attempts to avoid involvement with the new ACM / IEEE CS work on the creation of a new national Computer Science curriculum (due to unhappy experiences last time), Bruce ended up being pressed into service to chair the Programming Languages Knowledge Area Focus Group (KFG) for Curricula 2001 after the main committee had omitted the area completely. Alas, in spite of the KFG's attempts, the main curriculum committee decided that programming languages were no longer as relevant to core CS, slashing the curriculum coverage significantly compared to previous curricula. In an attempt to rally support for the area, Bruce and the committee published an article on the problems with the curriculum, and the KFG’s recommendations in the main publication of ACM’s Special Interest Group in Programming Languages. Bruce also served as a member of the Pedagogy Focus Group (PFG) on non-CS (primarily mathematics) requirements to the curriculum.

Assistant Professor Andrea Danyluk continued her research in Artificial Intelligence, specifically on issues arising from the application of Machine Learning to real-world problems. Last summer she focused her research on the investigation of systematic errors in data and how those errors affect inductive machine learning algorithms. That work has continued throughout this year.

Inductive machine learning algorithms extrapolate general trends from large data sets. It is generally assumed that the data to which the algorithms are applied are reasonably free of error. Inductive learning algorithms do accommodate for some noise in the data, but few studies exist that accurately address the effects of noise on the algorithms. Virtually no work has been done on characterizing the effects of systematic errors in data. Professor Danyluk received a NSF POWRE Grant in the amount of $74,352 to work on this topic over an 18-month period.

In the summer of 1999 three students worked with her, supported by the grant: Alfonso Gonzalez del Riego ’00, Steve Roman ’00, and Art Munson ’01. Professor Danyluk and her students designed a set of experiments to characterize the effects of different types of error on learning algorithms. They collected existing benchmark data sets; they also created artificial data sets that were used as controls. They then enumerated a variety of error types to investigate. They implemented a program to inject errors into selected data sets, and then ran those data sets through seven types of learning algorithms. Professor Danyluk presented results of that work in invited talks at Purdue University and the University of Massachusetts, Amherst.

Alfonso Gonzalez del Riego ’00 worked with Professor Danyluk in the fall as well. He investigated the possibility of classifying data according to style. Examples of such data might include music, users’ behaviors when logged into a computer, or bird song.

Professor Danyluk was invited to contribute to the Handbook of Knowledge Discovery and Data Mining, which will be published by Oxford University Press. She contributed a section on the application of Data Mining to telecommunications problems. Prior to coming to Williams, Professor Danyluk was a researcher with Bell Atlantic (formerly NYNEX), and she continues to collaborate on problems relevant to the telecommunications industry. She wrote her contribution with Foster Provost, Assistant Professor at the Stern School of Business at NYU (formerly of Bell Atlantic as well).

This year she had two papers published: “Problem Definition, Data Cleaning, and Evaluation: A Classifier Learning Case Study,” written with Foster Provost, and “Feature Selection vs. Theory Reformulation: A Study of Genetic Refinement of Knowledge-based Neural Networks,” with Brendan Burns, a former thesis student. (Brendan will be a Ph.D. student at the University of Massachusetts, Amherst, beginning this fall.)

In the summer of 1999, Professor Danyluk attended the Sixteenth National Conference on Artificial Intelligence and the International Conference on Knowledge Discovery in Databases. This year she was a member of the program committee for the International Conference on Machine Learning. She also reviewed books and research papers for Morgan Kaufman Publishers and for IEEE. Next summer she will co-chair the International Conference on Machine Learning with Professor Carla Brodley of Purdue University. The conference will be held at Williams College.

Professor Danyluk has been heavily involved in curricular issues this year, working on the redesign of CSCI 134, the introductory course in our department. She has also been involved in CC2001, an ACM and IEEE joint task force on computing curricula. She is a member of the Intelligent Systems focus group. Professor Danyluk also gave a talk for Spring Family Weekend entitled “Robots: State of the Art and Challenges for the Future.”

Professor Bill Lenhart continued to serve as chair of the department this year as well as serving as the Division III representative of the Committee on Appointments and Promotions and as a member of the Presidential Search Committee. Whenever he was not in meetings or teaching, he continued his work in algorithm design, focusing in particular on the problem of efficiently computing minimum-weight triangulations of planar point sets. During the academic year, he supervised the honors thesis research of Reed Townsend ’00 on the design of more efficient algorithms for computing triangulations of sets of co-circular points. Reed will begin working at Microsoft later this summer.

During the summer of 1999 Professor Lenhart served as a member of the program committee for Graph Drawing 99, the 7th International Symposium on Graph Drawing, which was held in September in the Czech Republic. He was also fortunate to be able to spend two weeks in Italy in January working with Giuseppe Di Battista and Giuseppe Liotta on a variety of problems related to the automated layout of graphs and diagrams. While there, he gave invited lectures at the Università degli Studi Roma Tre and at the Università degli Studi di Perugia on the problem of computing hamiltonian cycles in solid grid graphs.

Assistant Professor Barbara Staudt Lerner joined the Computer Science Department in fall 1999. She has a Ph.D. from Carnegie Mellon University and spent several years as a research assistant professor at the University of Massachusetts, Amherst. She specializes in software engineering, particularly the development and application of process programming languages to processes requiring the coordination of multiple people and tools operating in a distributed environment. Little-JIL, the process programming language she co-developed with researchers at the University of Massachusetts, Amherst was demonstrated at the International Conference on Software Engineering in June 2000. In addition, she served on the program committee for the European Conference on Object-Oriented Programming and as a reviewer for the Automated Software Engineering journal.

Professor Lerner has introduced a new software engineering elective to the department. The course focuses on the teaching the principles of software engineering by involving the class in the development of a large software project where the entire class works as a team, divided into groups, with each group working on a different aspect of the project. In spring 2000, the software engineering course developed an online portfolio management program to be used at the Center School in Greenfield, Massachusetts to allow elementary school students to develop online portfolios of their work and to allow teachers to review these works online.

Professor Murtagh worked with Chris Richards ’00 on the development of techniques to implement object-oriented languages in which the rules that determine when one class is a subtype of another are independent of the mechanism of inheritance. This is one of the features of the LOOM programming language developed by Professor Bruce and his students. In more conventional object-oriented languages, the relationship between inheritance and sub-typing simplifies the task of memory layout in an implementation. Multiple inheritance complicates the memory layout task, but completely separating inheritance from sub-typing makes the problem much more difficult. Murtagh and Richards developed a hybrid memory layout technique based on the introduction of a layer of indirection that provides reasonable worst-case behavior while making it possible to apply graph coloring techniques to ensure very efficient access to many object components. Richards worked on applying these techniques to an implementation of the LOOM language.

Class of 1960 Scholars in Computer Science

Jason Healy ’00

Kevin O’Connor ’00

Christopher Richards ’00

Reed Townsend ’00

Joseph Bergeron ’01

M. Art Munson ’01

Jessica Scott ’01

Yvonne Stone ’01


COMPUTER SCIENCE COLLOQUIA

Computer Science Faculty, Williams College

“Graduate School in Computer Science”

James T. Oates, University of Massachusetts

“Embodied Language Learning: Experiments in Language Acquisition with a Mobile Robot”

Chris Umans ’96, University of California, Berkeley

“The Complexity of Circuit Minimization”

Dr. Dannie Durand, Princeton University

“Rearrangements and Duplications in Genome Evolution”

Professor Paul Utgoff, University of Massachusetts

“Comprehensibility of Decision Trees”

Lisa Masterman Michaud ’95, University of Delaware

“Human-Computer Interaction and the Design of an Intelligent Tutor”

Professor Richard Salter, Oberlin College & University of Maryland

“Making History”

Professor Claire Cardie, Cornell University

“Noun Phrase Coreference for Information Extraction”

Todd W. Neller, Stanford University

“How to Stall a Motor: Information-Based Optimization for Safety Refutation of Hybrid Systems”

Justus Piater, University of Massachusetts, Amherst

“Learning Visual Discrimination for Real-World Tasks”

Lucia K. Dale, Texas A&M University

“Optimization Techniques for Randomized Motion Planning”

Dr. Casey Boyd, Intel Corporation

“Virtual Environment Design and Usability”

Professor Dexter Kozen, Cornell University
Class of 1960’s Scholar

“Language-Based Security”
“Is Hoare Logic Obsolete?”

James Teresco, Rensselaer Polytechnic Institute

“Structures and Algorithms for Large-Scale Parallel Adaptive Scientific Computation”

Professor Rodney Brooks,
Fujitsu Professor of Computer Science, Massachusetts Institute of Technology

“A Discussion with Rodney Brooks: The Future of Robotics”

Computer Science Faculty, Williams College

“Faculty Research Talks”

Gary Sevitsky, Java Visualization Group, IBM T.J. Watson Research Center

“Using Information Exploration Techniques to Analyze Java Program Behavior”

Dr. Kathleen Fisher, AT&T Bell Labs

“Hancock: A Domain-Specific Language for Processing Signatures”

COMPUTER SCIENCE STUDENT COLLOQUIA

Paul Bethe ’00, Christopher Fairbanks ’00, Alfonso Gonzalez del Riego ’00, Daniel Mason ’00, Miles Munson ’01, Christopher Richards ’00, Esteban Roman ’00

“Computer Science Majors Talked about Their Summer Work Experience – Part I”

Aaron Berman ’01, Charles Hagenbuch ’00, Jason Healy ’00, Yvonne Stone ’01, Reed Townsend ’00, Robin Yan ’00

“Computer Science Majors Talked about Their Summer Work Experience – Part II”

Reed Townsend ’00

“Exploring Co-Circular Point Sets and the Minimum-Weight Triangulation Problem”

Jason Healy ’00

“Automatic Generation of Penrose Empires”

Reed Townsend ’00

“Co-Circular Points Sets and the Minimum Weight Triangulation”

OFF-CAMPUS COLLOQUIA

Kim B. Bruce

"A Library to Support a Graphics-Based Object-First Approach to CS1", ECOOP 2000 Workshop on Tools and Environments for Understanding Object-Oriented Concepts, 6/12/2000

Andrea Danyluk

“Characterizing the Effects of Systematic Data Error on Inductive Classifier Learning Algorithms”,
Purdue University, University of Massachusetts at Amherst

William Lenhart

“Efficiently Computing Hamiltonian Cycles in Solid Grid Graphs”, Università degli Studi Roma Tre, Università degli Studi di Perugia, January, 2000

POSTGRADUATE PLANS OF COMPUTER SCIENCE MAJORS


Paul M. Bethe

Unknown

Christopher J. Fairbanks

eZiba.com

Brad K. Geddes

Logistics Software, Boston

Alphonso Gonzalez del Riego

The Exeter Group, IT Consulting

Charles J. Hagenbuch

BiT Group, Inc. Boston

Jason B. Healy

BiT Group, Inc. Boston

Jason W. Holmes

The Exeter Group, Cambridge

Daniel M. Mason

NetMorf, Inc., Software Engineer

Viet Q. Nguyen

Oracle Corp., Application Developer

Christopher D. Richards

Princeton, Graduate Student

Daniel J. Richter

The Whitehead Institute

Esteban A. Roman

Multi-link, Boston (tentative)

Qiang Sun

Siebel Systems, San Mateo, CA

Reed L. Townsend

Microsoft, Software Design Engineer

Robin L. Yan

Travel abroad, then Graduate School 2001