COMPUTER
SCIENCE DEPARTMENT
Introductory Computing Lab
This past year Computer Science moved into its new facilities in the
Thompson Computing Laboratory, located on the second and third floors of TCL and
looking out over the Science Quad. Our new facilities allow faculty and
students to share a common suite of offices located near our two computing labs,
a science-wide computing lab, and a reconfigurable special purpose lab. Our
introductory lab is outfitted with Macintosh G4 processors, and our advanced lab
currently holds PC-based unix boxes, for use in advanced courses and research
Central to the department is a Common Room, fully wired for portable
computers.
We were pleased to have two new faculty join us this year. Assistant
Professor James Teresco is from RPI, and continues his research in parallel and
distributed computing. Also, Sean Sandys ’94 returned to Williams as a
Bolin Fellow. While here, he worked on his dissertation on specifying
communication in real-time systems and taught a semester of our introductory
programming course. Sean will take a long-term position at Olin School of
Engineering, the exciting new engineering college, and is due to begin teaching
within the next year. We wish him the best of luck!
Advanced Unix Lab
This has also been an exciting year for curricular innovation. Kim Bruce,
along with Andrea Danyluk and Tom Murtagh, received a new NSF CCLI grant,
“Making Interaction Fundamental in Object-Oriented CS 1.” The grant
for $287,892 will support the development of materials for CSCI 134, the
introductory course in computer science. In the summer of 1999, Bruce, Danyluk,
and Murtagh began designing a new approach to the introductory course. This new
approach uses Java as the programming language, and places a heavy emphasis on
event-driven programming and concurrency early in the course. The grant will
support the writing of a textbook for this course as well as further refinement
of the “objectdraw” library and other supporting software for the
course. In the spring of 2001, Cheng Hu ’03 worked on refinements of the
library. Krishna Kannan ’03 will continue this work in the summer of
2001. In August several faculty from other schools will be coming to Williams
to learn how to use our materials in preparation for teaching courses based on
this material in the 2001-2002 academic year.
Bruce, Danyluk, and Murtagh made several presentations on their new
approaches to introductory Computer Science courses. Bruce presented a paper
from the group, “A Library to Support a Graphics-Based Object-First
Approach to CS 1” at the SIGCSE 2001 Symposium on Computer Science
Education in February in Charlotte, North Carolina. Bruce was also the co-author
with Charles Keleman of Swarthmore College and Allen Tucker of Bowdoin College
of another paper presented at the same conference, “Our Curriculum Has
Become Math-Phobic!” Bruce, Danyluk, and Murtagh presented a three hour
workshop titled “Events and Objects First: an Innovative Approach to
Teaching Java in CS 1” at the Northeast conference of the Consortium for
Computing in Small Colleges in April 2001, at Middlebury College in Vermont.
Finally, Murtagh will present another paper co-authored by the group,
“Event-driven Programming Can Be Simple Enough for CS 1” at the
Symposium on Innovation and Technology in Computer Science Education in June
2001, in Canterbury, England.
Professor Kim Bruce continued his research on extending the expressiveness
of object-oriented languages while 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 2000, John “Nate” Foster worked with Bruce
on extending Sun’s Java compiler to support a more expressive type system.
This work was an extension of Jon Burstein’s thesis from 1998. The summer
work involved detailed examination of the encoding of new language constructs
into a form understandable by the Java virtual machine.
Nate continued with this work as his honors thesis, writing a very nice
thesis describing further extensions to Java and their implementation. The
added expressiveness added by these features helps programmers express their
ideas more naturally in object-oriented languages. Nate will stay around during
the summer of 2001 to put in further work on this project before heading to
Cambridge University for two years on a Herschel Smith Fellowship.
Cheng Hu will also work with Bruce this summer on a project that will
eventually result in modifying the Java Virtual Machine Language to better
support parametric polymorphism and other advanced language features. During
the fall of 2000, Aaron Berman ’01 and Darren Creutz ’01 worked with
Professor Bruce on ideas in language design and implementation as part of a
research course.
Bruce’s main research work during the last year continued to be
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. The
manuscript will be sent to MIT Press sometime during the summer of
2001.
Bruce stepped down as chair of the organizing committee for the
International Workshops on Foundations of Object-Oriented Languages (FOOL),
after the 8th workshop, held this year in London in association with the ACM
Symposium on Principles of Programming Languages. For these efforts, he
received an ACM Recognition of Service award for the fourth time. He will
continue on the organizing committee of FOOL for one more year.
Bruce served on the program committee for the February 2001 meeting of the
New England Programming Languages Symposium (NEPLS) at Boston University. In
May 2001, Professor Bruce hosted the summer meeting of NEPLS at Williams
College. Professor Bruce remains on the program committee for the fall 2001
meeting of NEPLS at Sun Microsystems.
Having co-chaired the ad hoc Technology Committee’s investigation of
distance learning in 1999-2000 at Williams, Bruce was invited in the summer of
2000 to make a presentation on distance learning and liberal arts colleges at a
meeting of Vice-Presidents for Advancement (development) from about 10 liberal
arts colleges at Mount Holyoke College. He also gave a talk on distance
education at the 2000 Williams College alumni reunions.
This fall Professor Bruce taught CSCI 134, Introduction to Computer
Science, with Professor Barbara Lerner. This innovative course continues to
work well. Bruce and Lerner put extensive lecture notes on the web for student
use. In the spring, Bruce taught CSCI 256, Algorithm Design and Analysis. The
course syllabus was revised to provide more coverage of flow problems and
complexity results involving computer circuits.
Bruce was involved in several other activities through the last academic
year. He served as outside evaluator in two tenure cases this fall, and as
referee for several research papers and proposals for introductory texts in
Computer Science. He served as an external reviewer for the Computer Science
Department at Transylvania University in Lexington, Kentucky. He served on the
program committee for the 2001 International Conference on Automata, Languages,
and Programming. He continues to serve on the steering committee for the
International Conference on Functional Programming. He attended the POPL 2001
meeting in London in January 2001 and the OOPSLA meeting in Minneapolis in
October.
Associate Professor Andrea Danyluk continued her research in Artificial
Intelligence, specifically in the area of Machine Learning. Danyluk’s
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 database of
cancer patients’ records, for instance, to determine general rules that
might predict for the recurrence of a particular type of cancer. This year
Prof. Danyluk considered the use of such algorithms for the purpose of
re-engineering existing knowledge-based systems. Knowledge-based systems are
programs that are designed to perform some type of expert task, such as
diagnosis. They are called “knowledge-based” because of the vast
amount of human expert knowledge that must be explicitly encoded in them. Many
such systems were developed in the 80’s. They are extremely complex and
difficult to understand. In many cases, the original developer of a system is
no longer available to explain how it functions. Even if the original developer
were available, any given knowledge-based system has probably been modified so
much over the years that its underlying knowledge has become opaque.
Inductive machine learning algorithms can be applied in these cases to
build a model that summarizes the behavior of the knowledge-based system.
Together with Professor Foster Provost at New York University, Danyluk is
completing a paper on the success of this method of re-engineering legacy
knowledge-based systems.
This summer she is beginning a new project that involves the automatic
classification of business news stories (into such categories as
“mergers” or “acquisitions,” for example). This is part
of a larger project in collaboration with Dr. Provost. Josh Ain ’03 and
Rob Gonzalez ’03 are working with her on the project.
In the summer of 2000, Danyluk served as a member of the program committee
for ICML, the International Conference on Machine Learning. This year she is
co-chairing ICML with Professor Carla Brodley of Purdue University. This
conference will bring 250 leading researchers together to present their work and
exchange ideas. The conference will take place at Williams College from June 28
through July 1.
In addition to her work on this conference, Danyluk has also served on the
program committee for FLAIRS-2001, the Florida Artificial Intelligence Research
Symposium, and has been a reviewer for the journal Systems, Man, and
Cybernetics, as well as for Morgan Kaufmann Publishers.
She also substantially redesigned the department’s elective on
Artificial Intelligence. The course begins with an introduction to fundamental
algorithms and knowledge representations. The second half provides an in-depth
look at machine learning algorithms. The course now includes a component on
robotics as well.
Professor Bill Lenhart stepped down from the CAP and, escaping the role of
chair for a year, was able to take a mini-sabbatical during the spring semester.
While on sabbatical, he continued his research in graph theory, graph drawing,
and began to investigate some new directions for his scholarship. In February,
Lenhart presented a lecture entitled “Geometric Graphs, Graph Drawing and
Minimum Weight Triangulations” at both Clark University and
Worcester Polytechnic Institute. In September, the paper “Minimum Weight
Drawings of Maximal Triangulations”, co-authored with Giuseppe
Liotta, was presented at GD 2000, the 8th International Symposium on Graph
Drawing, held in historic Williamsburg, Virginia. In March, the paper
“Bichromatic P4 Composition Schemes for Perfectly
Orderable Graphs”, co-authored with Ryan Hayward, was presented at
the Brazilian Symposium on Graphs, Algorithms and Combinatorics, held in
Fortaleza, Ceara, Brazil. A paper entitled “The Drawability Problem for
Minimum Weight Triangulations”, co-authored with Giuseppe Liotta, was
accepted for publication in the journal Theoretical Computer Science. In
June, Lenhart attended the 17th Annual ACM Symposium on Computational Geometry
held at Tufts University.
Assistant Professor Barbara Staudt Lerner was awarded a three-year NSF
grant to study the problem of usability of software process programs. Software
process programs enable an organization to describe its processes formally,
allowing such benefits as repeatability, automation of routine tasks,
enforcement of standards, analysis and improvement. Current process programming
languages offer semantics that are rich enough to describe the necessary
concepts but provide weak support for user interaction. As a result, software
process programs are rarely actually executed by the people carrying out the
process, with the result that many of the benefits of formally describing the
processes are lost. The goal of the research is to improve the usability of
these programs so that their benefits can be more fully realized.
Lerner presented “Using Little-JIL to Coordinate Agents in Software
Engineering” at the 15th IEEE International Conference on Automated
Software Engineering in Grenoble, France. The paper was co-authored with
researchers from the University of Massachusetts, Amherst and describes the
Little-JIL process programming language, a graphical language designed to allow
multiple human and software agents executing in a distributed environment to
cooperate in the execution of a complex task.
During the course of the year, Professor Lerner worked with Carli Malcolm
’01 on two projects. The first project involved modifying Argo, UML
design tool developed at UCI Irvine. A unique feature of Argo is its use of
design critics, which provide advice on how to improve an object-oriented
design. Carli’s work involved introducing a software design process into
Argo so that the criticisms would be given in a more timely manner.
Carli’s second project involved developing two agenda viewers for use
during the execution of Little-JIL process programs. The first used e-mail to
notify a user when they had been assigned a task during the execution of a
process. The second provided a Web-based user interface to allow interaction
with a process program.
Assistant Professor James D. Teresco completed his Ph.D. Dissertation in
July 2000: “A Hierarchical Partition Model for Parallel Adaptive Finite
Element Computation” at Rensselaer Polytechnic Institute. His advisor was
Joseph E. Flaherty.
Teresco, in collaboration with Flaherty, received a $150,000 grant funded
through Sandia National Laboratories to support research of “Dynamic Data
Management and Load Balancing for Parallel Adaptive
Computation.”
Teresco recently purchased a 20-processor Sun Microsystems computer cluster
to be installed at Williams in Summer 2001 to support research in parallel and
distributed computing in the Computer Science Department.
In addition, Teresco participated in peer review for SIAM Review and
Scientific Programming journals this past year. He participated in peer
review for a conference as well, attending the International Parallel &
Distributed Processing Symposium.
Professor Duane Bailey worked with Art Munson ’01 to better
understand the effect of caches on the implementation of hardware for directly
supporting the execution of Java. Because a primary goal of Java is
portability, it often cannot make use of platform-specific architectural
features. Munson and Bailey demonstrated that some novel caches can speed Java
without changing the way Java is currently compiled or executed. Bailey is
currently working on a web-based environment to support computer animation.
Bailey was the workshop, panels, and tutorials chair for CCSCNE 2001 in
April.
Class of 1960 Scholars in Computer Science
Aaron Berman
|
Darren Creutz
|
Nate Foster
|
Asako Kohno
|
Carlett Malcolm
|
Art Munson
|
Samantha Orme
|
Yvonne Stone
|
COMPUTER SCIENCE
COLLOQUIA
Professor Donald Knuth, Professor Emeritus at Stanford University
“Dancing Links”
Computer Science Faculty, Williams
College
“Graduate School in Computer Science”
Professor Andrea
Danyluk, Department of Computer Science, Williams College
“Characterizing the Effects of Systematic Data Error on Inductive
Classifier Learning Algorithms”
Professor Robert Dewar, New York
University
“Software Copyrights and Patents and Free
Software”
Professor Williams Wootters, Physics, Williams
College
“Computing in Parallel Worlds: The Quantum Search
Algorithm”
Class of 1960’s Speaker, Dr. Susan Landau, Sun
Microsystems Laboratories
“Cryptology, Technology, and Policy” and “Designing
Cryptology for the Twenty-First Century”
Sean Sandys, 1994, Williams
College and University of Washington
“Requirement Specifications for Distributed Real-Time
Communication”
Professor William Lenhart, Department of Computer
Science, Williams College
“Geometric Graphs, Graph Drawing, and Minimum-Weight
Triangulations”
Professor Barbara Lerner, Department of Computer
Science, Williams College
“Coordination of Human and Computer Agents”
Professor James
Teresco, Department of Computer Science, Williams College
“Partitioning and Load Balancing for Parallel Adaptive Scientific
Computation”
Class of 1960’s Speaker, Professor Larry L.
Peterson, Department of Computer Science, Princeton University
“Preliminary Experience Implementing an Extensible
Router”
Ms. Allison Klein, Princeton University
“Video Cubism”
Dr. Donald H. House, Professor of
Architecture and Coordinator of the Master of Science Visualization Sciences
graduate program at Texas A & M University’s Viz Lab
“Automatic Construction of Continuous Area Cartograms”
Ms.
Kristin P. Bennett, Mathematical Sciences Department, Rensselaer Polytechnic
Institute”
“Support Vector Machines: Hype or Hallelujah?”
COMPUTER SCIENCE
STUDENT COLLOQUIA
J. Nate Foster ’01, Aaron Berman, ’01 Masato Sudo ’01,
Ethan Katz-Bassett ’01 and Grayson Myers ’01
Computer Science Majors talked about their summer work experiences (Part
1.)
M. Art Munson ’01, Michael Chanin ’01, Shimon Rura ’03,
Yvonne Stone ’01, and Carlett Malcolm ’01
Computer Science Majors talked about their summer work experiences (Part
2.)
M. Art Munson ’01
“Caching, the Java Virtual Machine and Why They Don’t Like Each
Other”
Aaron Berman ’01
“Encoding LOOM Objects in a Typed Intermediate Language”
J.
Nate Foster ’01
“Languages Don’t Have Shrinks; How to Increase Java’s
Expressiveness so It Plays Nice with Programmers”
OFF-CAMPUS
COLLOQUIA
William Lenhart
“Geometric Graphs, Graph Drawing and Minimum Weight
Triangulations”
Clark University and Worcester Polytechnic Institute, February 2001
Kim
B. Bruce
“A Library to Support a Graphics-Based Object-First Approach to CS 1,
“SIGCSE 2001, February 2001, Charlotte, North Carolina
Kim B. Bruce
(with Professors Andrea Danyluk and Tom Murtagh)
Workshop on “Events and Objects First: An Innovative Approach to
Teaching Java in CS 1”, CCSCNE, April 2001, Middlebury College,
Middlebury, Vermont
POSTGRADUATE PLANS OF DEPARTMENT MAJORS
Aaron Berman
|
|
Michael Chanin
|
Goldman Sachs, New York City
|
John Nate Foster
|
Cambridge University, Graduate School
|
Sebastian Gruender
|
Merrill Lynch, New York City
|
Kevin Hong
|
|
Ethan Katz-Bassett
|
|
Asako Kohno
|
|
Carlett Malcolm
|
New York City
|
M. Art Munson
|
Microsoft, Seattle, WA
|
Grayson Myers
|
|
Williams Ronco
|
Travel, Undecided
|
Jessica Scott
|
|
Masato Sudo
|
Microsoft, Seattle, WA
|
Steven Wollkind
|
|