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
|