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:
Class of 1960 Scholars in Computer Science
Robin Stewart
|
Lee Wang
|
Bartley Tablante
|
Laura Effinger-Dean
|
Philip Enock
|
Michael Gnozzio
|
Jessica Chung
|
Alexandra Constantin
|
Marcus Duyzend
|
Reid Lynch
|
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 5th 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 COLLOQUIA
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”
COMPUTER SCIENCE STUDENT COLLOQUIA
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”
OFF-CAMPUS COLLOQUIA
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
POSTGRADUATE PLANS OF COMPUTER SCIENCE MAJORS
Daniel Berger
|
Med Trak, Philadelphia, PA
|
Christopher Douglas
|
Undecided
|
Philip Enock
|
Organizer of a rock band, Technical Consultant, New York, NY
|
Charles Giammattei
|
Med Trak, Philadelphia, PA
|
Marina Lifshin
|
Undecided
|
Ashok Pillai
|
Teacher of Math, St. Sebastian’s School, Needham, MA
|