COMPUTER SCIENCE DEPARTMENT

RepSci200108.jpg
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!


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