COMPUTER SCIENCE DEPARTMENT

The 1998-99 academic year was a very eventful one for the department. Professor Bill Lenhart replaced Professor Kim Bruce as chair, allowing Professor Bruce to take a well-earned sabbatical. On an equally well earned sabbatical this year was Associate Professor Duane Bailey. Filling in for them were Visiting Assistant Professor Jay Sachs, returning to the department for a second year, and Visiting Assistant Professor Marton Balazs, who joined us for the year from the Worcester Polytechnic Institute. Rounding out the department were Assistant Professor Andrea Danyluk, who had just returned from a very productive sabbatical, and Professor Tom Murtagh.

The growth of the department continues unabated. On the faculty side, we were delighted to have been able to welcome a new member to the department. Assistant Professor Barbara Staudt Lerner, currently at UMass Amherst, has accepted a position on the faculty and will be joining the department this fall. Professor Lerner’s area of research is Software Engineering, and she will be offering a junior-level elective on the topic this coming spring. Enrollments and the number of majors also remained high. There were 21 Computer Science majors in the graduating class this year, our largest group yet. This coming year we will have 15 senior majors and 15 junior majors. Our courses for non-majors also continued to grow in popularity; in particular, CSCI 105: Understanding the Web: Technologies and Techniques, attracted over 150 registrations for the 95 available openings in the course. And with the introduction of a robotics component, CSCI 108: Artificial Intelligence: Image and Reality, promises to become another very popular course for non-majors.

The robot-building CSCI 108 class with one of the robots (inset)

The department places a high priority on involving undergraduates in research. As happens every year, students worked with members of the department on various projects this past summer. Joe Vanderwaart ‘99 worked with Professor Bruce on the design and implementation of better object-oriented programming languages. Neelay Shah ‘99 worked with Professor Murtagh on problems in digital watermarking of images. Reed Townsend ‘00 and Joshua Fincke ‘99 worked on preparing materials for CSCI 105: Understanding the Web, under the supervision of Professor Murtagh. The work of the research assistants is described below in the descriptions of faculty research. In addition, Alfonso Gonzalez del Riego ‘00 worked for the department last summer under the supervision of Systems Support Specialist Mary Bailey. This summer, Carlett Malcolm ‘01 will be replacing Alfonso in that position.

Three students pursued honors research this past year. Marc Blackstein ‘99 worked with Professor Lenhart to develop faster algorithms for finding minimum-weight triangulations of point sets; Neelay Shah ‘99 worked with Professor Murtagh on techniques for digital watermarking of images; and Joe Vanderwaart ‘99 worked with Professor Bruce on object-oriented language design and implementation.

Members of the department were also involved in educational activities beyond the College community. Professor Bruce, Professor Bailey, Mary Bailey, and Professor Murtagh organized and taught a summer workshop for local high school and middle school students last summer. The program was designed to introduce the students to a variety of aspects of digital technology related to the web. Topics included HTML, image processing software and Javascript programming. The workshop ran for one week in August. Each morning, a new topic was presented through a guided, hands-on project. In the afternoon, the instructors provided guidance to students working on projects of their own design. Professor Bailey, Mary Bailey, Professor Murtagh, and Professor Sachs also offered a course this past July on various web technologies to local teachers. The course is one of several that are offered by Williams each year as part of an ongoing program to support elementary and secondary education in local communities.

Associate Professor Duane Bailey continued his work on the study of data structures for supporting quasicrystals---a form of crystal that potentially exhibits long range symmetries not considered possible by classical theories. He visited researchers at Smith College, the University of Washington, Microsoft and Intel in the process of evaluating new directions for further work with students in fall of 1999. Professor Bailey will be giving a talk at Reed College this June at the CLAC (Consortium of Liberal Arts Colleges) conference. He will be discussing the use of computers to help visualize new approaches to traditionally difficult problems in the sciences.

In preparation for a new tutorial course to be offered in the spring of 2000 on the design of modern architectures, Professor Bailey took two graduate courses at the University of Massachusetts in electrical engineering. At UMass he worked with undergraduates to design and fabricate a single chip for performing high-speed modular exponentiation of numbers. Within the chip, a parallel systolic array is used to accelerate the computation of very large products. Such chips form the heart of high-performance hardware encryption devices. He is also in negotiations with Intel to begin the development of a VLSI design laboratory at Williams.

Professor Bailey spent much of his leave completing his new introductory text in Java programming, Java Elements, to be published by McGraw-Hill in summer of 1999. This text is the first of a two book series written especially for students of the liberal arts. The second volume, Java Structures, has already met with great success.

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

During the summer of 1998, Joe Vanderwaart ‘99 once again worked with Professor Bruce on refining the design and implementation of the object-oriented language, LOOM; in particular, to extend the design of LOOM to better support the use of inheritance with closely integrated systems of classes and objects. In the spring of 1998, Bruce, Odersky, and Wadler proposed an extension of Java to support this increased expressiveness. The work during the summer involved working out all of the details of the type system and implementation of virtual types in the language LOOM. Professor Bruce, along with Joe Vanderwaart, and Leaf Petersen ‘96 co-authored a technical report on the module system for LOOM. He also worked with Chris White ‘00 during the summer of 1998 on extending the honors work of Jon Burstein ‘98 in the design and implementation of an extension of Java which will support parametric polymorphism and a “MyType” construct.

During the fall semester of his sabbatical, Professor Bruce taught a Programming Languages course at Princeton University and consulted at the NEC Research Center in Princeton on the design of a typed intermediate language for Java. He was in residence in Williamstown in the spring during which time he worked on the manuscript of a monograph on his research. Professor Bruce’s work in the fall with NEC resulted in one of the first typed intermediate languages designed for object-oriented languages (in this case, Java).

Joe Vanderwaart ‘99 worked with Professor Bruce this year on an honors thesis that also had to do with typed intermediate languages for object-oriented languages. Professor Bruce’s work at NEC involved the design of a relatively high-level object-based intermediate language. Joe’s work, by contrast, involved compiling to a lower-level intermediate language which is similar to that used by researchers working with functional languages. The hope is eventually to connect Joe’s implementation to the back-end of Yale’s FLINT compiler, which is currently used with the SML of NJ compiler. Joe will be working on similar research next year as a graduate student at Carnegie-Mellon University, where his study will be supported by an NSF graduate fellowship.

Professor Bruce had three papers accepted at refereed conferences in 1998-99. The first paper, “A Statically Safe Alternative to Virtual Types,” was co-authored with Martin Odersky and Phil Wadler. It was presented at ECOOP ‘98 in July in Brussels. The second, “Formal Semantics and Interpreters in a Principles of Programming Languages Course,” was presented at the ACM SIGCSE Technical Symposium on Computer Education in New Orleans in March. The paper discussed some unusual assignments used in the Principles of Programming Languages course at Williams. The last paper, “Semantics-Driven Language Design: Statically Type-Save Virtual Types in Object-Oriented Languages,” was co-authored with Joe Vanderwaart and was presented at the conference on Mathematical Foundations of Programming Systems in April in New Orleans.

In addition to all of this, Professor Bruce gave a talk on “Grouping Constructs & Semantics in Object-Oriented Languages” at the Dagstuhl Seminar on The Semantic Challenge of Object-Oriented Programming in Wadern, Germany in July of 1998. He also gave an invited talk titled, “CS 2: How did we get here? Where should we be going?” at the OOPSLA Workshop on the Future of CS 2 and Data Structures. In September he gave an invited talk titled “Semantics-driven language design: Statically type-safe virtual types in object-oriented languages” at the New Jersey Programming Languages Seminar at the NEC Research Institute, Princeton, NJ. During the year, he also presented talks on his research on virtual types and module systems for object-oriented languages at Computer Science colloquia at the University of Pennsylvania, Yale University, Cornell University, Boston University, Swarthmore College, and Bell Laboratories. He gave half-day tutorials on the design of statically type-safe object-oriented languages at ECOOP ‘98 in Brussels and OOPSLA ‘98 in Vancouver. He also gave a talk to an alumni group in Rochester in March on “Computers, the Internet, and Everything.”

Professor Bruce also served as the external reader for a Ph.D. thesis at the Free University of Brussels in the summer of 1998, and served on a visiting committee in mathematics and computer science at Simmons College in Boston in November. He continued as chair of the organizing committee of the Workshop on the Foundations of Object-Oriented Languages (FOOL 6), held in January in San Antonio, Texas, and co-edited a special issue of the journal “Theory and Practice of Object-Oriented Systems” containing the best papers from the FOOL 5 workshop. He is now editing a special issue of Information and Computation that will contain the best papers from FOOL 6. Miscellaneous other activities included reviewing book manuscripts for publishers and refereeing papers submitted to conferences and journals.

Assistant Professor Andrea Danyluk continued her research in Artificial Intelligence, specifically on issues arising from the application of Machine Learning to real-world problems. This year the focus of her research was in exploring the effects of systematic data error on inductive machine learning algorithms.

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 the data. Professor Danyluk has received a NSF POWRE Grant in the amount of $74,352 to work on this topic over an 18-month period. She is addressing two major questions in this work: 1) What are the effects of different types of systematic data error on existing machine learning algorithms? and 2) Is it possible to detect systematic data error when it exists? A short position paper on these issues appeared in the Working Notes of the Workshop on Keys to the Commercial Success of Data Mining, held in conjunction with the International Conference on Knowledge Discovery in Databases last summer.

Several students are involved in this work. Alex Eaton-Salners ‘99 began to investigate the problem of detecting systematic error in an Independent Study during the Fall ‘98 semester. Three students will be working with Professor Danyluk during the summer of ‘99. They are Alfonso Gonzalez del Riego ‘00, Steve Roman ‘00, and Art Munson ‘01.

Professor Danyluk continued to work with Brendan Burns ‘98, who had been her thesis student last year. Together they wrote a paper entitled “Feature Selection vs. Theory Reformulation: a Study of Genetic Refinement of Knowledge-based Neural Networks,” which has been accepted for publication in the journal Machine Learning.

Last year, together with Dr. Foster Provost and Dr. Tom Fawcett, researchers at Bell Atlantic, she began a new research project with a focus on Time-Series Analysis. In the summer of ‘98, Professor Danyluk chaired a workshop on “AI Approaches to Time-series Problems,” held in conjunction with both the National Conference on AI and the International Machine Learning Conference. Drs. Provost and Fawcett were also members of the organizing committee. Their summary of the workshop appeared in AI Magazine. The proceedings of the workshop have been turned into an AAAI (American Association for Artificial Intelligence) technical report. Professor Danyluk, with Dr. Provost, also had a paper accepted by the journal Informatica. The paper is entitled “Problem Definition, Data Cleaning, and Evaluation: A Classifier Learning Case Study.” In addition, Professor Danyluk discussed her research in two Sigma Xi Faculty Lectures in the spring.

This year Professor Danyluk taught four courses, Artificial Intelligence, Theory of Computation, Data Structures and Advanced Programming, and Artificial Intelligence: Image and Reality. The last of these is an introductory level course for non-majors. Professor Danyluk revised this course substantially from previous offerings. Most of the course focussed on robotics, with groups of students building and programming their own robotic vehicles. The robot vehicles were built around the Handy Board, a processor for running robotic applications that was developed at the MIT Media Lab. Over the course of the semester the students put their vehicles together, soldering wires and connectors for motors and various types of sensors. They then programmed the vehicles. The robots and more specific details about the course can be found by starting at Professor Danyluk’s Home Page: http://www.cs.williams.edu/~andrea/.

While a great deal of his time this year was spent chairing the department and serving on the Faculty Steering Committee and later, the Presidential Search Committee, Professor Bill Lenhart managed to find some time to devote to his continuing work in algorithm design and analysis. His research currently focuses, for the most part, on graph drawing algorithms, that is, methods for automated layout of diagrams. He attended GD ‘98, the 6^th International Symposium on Graph Drawing, this past August in Montreal, Quebec. This coming year he is serving on the program committee for GD ‘99, which will be held this September, in Prague, Czech Republic. This past summer Professor Lenhart also attended CCCG ‘98, the Tenth Annual Canadian Conference on Computational Geometry, which was also held in Montreal.

Professor Lenhart supervised two undergraduate honors theses this year, one in the Computer Science Department and one in the Mathematics Department. He worked with Marc Blackstein ‘99 on the problem of finding more efficient algorithms for computing minimum-weight triangulations of point sets in the plane. Marc was able to improve the performance of the best-known algorithm for this problem by designing an optimal algorithm for computing the number of empty triangles in an arbitrary finite point set. He implemented his improved version of the algorithm in Java, and it currently runs as part of the Zarbiff system (developed a few years ago by some of our majors) for editing and visualizing graphs. Later this summer, Marc will be pursuing his computing interests at Intel in Portland. Professor Lenhart also worked with Davina Kunvipusilkul ‘99 on developing an algorithm for laying out graphs on a hexagonal grid so that the number of bends along edges of the graph is minimized. Davina was able to develop such an algorithm for series-parallel planar graphs of maximum degree at most six. She will be entering the Ph.D. program in Operations Research this fall at Cornell.

Professor Tom Murtagh recently began a research project in the area of digital watermarking. Digital watermarks are an example of the application of techniques designed to enable one to hide some small piece of information in the encoding of a larger “host” document. In the case of digital watermarking the purpose of the hidden information is to prevent copyright infringement by identifying the owner of the host document. To be effective, the encoding techniques used to hide a digital watermark must make it difficult for anyone other than the owner of the document to remove the identifying information from the document. Professor Murtagh supervised Neelay Shah ‘99 in the completion of an honors project in this field. He and Neelay experimentally compared the resilience of several proposed watermarking techniques to transformations intended to remove the watermark from the host document.

Professor Murtagh also attended the SIGPLAN Programming Language Design and Implementation Symposium at the 1999 Federated Computing Research Conference in Atlanta, Georgia.

Joseph Vanderwaart ‘99, Charles Hagenbuch ‘00, Neelay Shah ‘99, Daniel Sullivan ‘99, Michael Sullivan ‘99, Christopher White ‘00

Williams College

“Computer Science Majors Talked about Their Summer Work Experience”

Professor Lawrence Snyder

University of Washington

Class of 1960’s Scholars Speaker

“‘WWW’ Is Not Short For ‘World Wide Web,’ And Other Stuff Everyone Should Know about Computers”

Professor Lawrence Snyder

University of Washington

Class of 1960’s Scholars Speaker

“The Principles of ZPL”

Dr. William D. Shannon

Washington University School of Medicine

“Combining Classification Trees Using Maximum Likelihood Estimation”

Department of Computer Science Faculty

Williams College

“Graduate School in Computer Science”

Professor David Goldsman

Georgia Tech School of Industrial and Systems Engineering

“Procedures for Selecting the Best System”

Dr. Michael Reed

Columbia University

“Computer Modeling of Real-World Objects: An Approach to Automatic Shape Reconstruction Using Range Images.”

Professor David Jensen

University of Massachusetts, Amherst

“The Ghost in the Machine: How a Simple Statistical Error Causes Machine Learning Algorithms to Be Superstitious.”

Dr. Foster Provost

Bell Atlantic Science and Technology

“Robust Classification Systems for Imprecise Environments”

Gary Sevitsky

IBM Watson Research Center

“What Is That Java Program Really Doing: Using Information Exploration Techniques to Understand Program Behavior”

Marc Blackstein ‘99

Williams College

“Triangulations, Empty Triangles, and Output Sensitive Algorithms”

Neelay Shah ‘99

Williams College

“The Comparison of Watermarking Techniques”

Joseph C. Vanderwaart ‘99

Williams College

“LOOM into FLINT (almost): Typed Intermediate Representations for Compiling Object-Oriented Languages”

Alex Eaton-Salners ‘99

Williams College

“Using Conceptual Clustering to Identify Systematic Data Error”

Zachary Dodds

Yale University

“Making Robots Do What They See”

Monica Brockmeyer

University of Michigan

“Real-Time Specifications: Tools and Techniques for Improving Scalability”

Dr. Carlo C. Maley

University of New Mexico

“The Evolution of Biodiversity”

Dr. Ken Stanley

“Petaflops, Teraflops and Less: High Performance Scientific Computation”

Dr. Barbara Staudt Lerner

University of Massachusetts, Amherst

“From Software Development to Software Engineering: Making Software Process Explicit”

Professor Andrea Danyluk

Williams College

Sigma Xi Talks

“Machine Learning: Background and Recent History”

“Data Mining and Other Applications of Machine Learning”

Stina Bridgeman

Brown University

“Interactive Graph Drawing and Similarity Metrics”

Professor Adam Finkelstein

Princeton University

Class of 1960’s Scholars Speaker

“Texture Mapping for Cell Animation”

Computer Science Faculty

Williams College

“Research in Computer Science”

Professor Carla Brodley

Purdue University

“Applying Machine Learning in Practice”

Kim Bruce

“Grouping Constructs & Semantics in Object-Oriented Languages” at the Dagstuhl Seminar on The Semantic Challenge of Object-Oriented Programming in Wadern, Germany
University of Pennsylvania

“A Statically Safe Alternative to Virtual Types” ‘98, Brussels, Belgium

“A Statically Safe Alternative to Virtual Types”
Tutorials at ECOOP ‘98, Brussels, Belgium and OOPSLA ‘98

“Semantics-Driven Language Design: Statically Type-Save Virtual Types in Object-Oriented Languages”
New Jersey Programming Languages Seminar, Princeton, NJ

“Modules in Object-Oriented Languages”
University of Pennsylvania

“CS 2: How Did We Get Here? Where Should We Be Going?”
OOPSLA Workshop on the future of CS2 and Data Structures

“LOOM: An Advanced Type System for Object-Oriented Programming Languages”
Yale University

“Designing Expressive, Yet Safe, Object-Oriented Languages”
Swarthmore College

“Statically Type-Save Virtual Types: Adding Expressiveness and Safety in Object-Oriented Languages”
Boston University, Cornell University, and Bell Laboratories, Murray Hill, NJ

“Computers, The Internet, and Everything”
Williams College Alumni meeting, Rochester, NY

“Semantics-Driven Language Design: Statically Type-Safe Virtual Types in Object-Oriented Languages”
Mathematical Foundations of Programming Semantics Conference, New Orleans, LA

Zehra Abid: Information Tech Consultant for The Exeter Group, Cambridge, MA

Luis J. Baldivieso: Unknown

Matthew R. Bell: Programmer/Consultant for The Exeter Group, Cambridge, MA

Marc S. Blackstein: Rotation Engineer for Intel, Portland, OR

John J. Coffey Software Engineer for Lockheed Martin’s Management and Data Systems Group, Fairfax, VA

Alexander Eaton-Salners: Undecided

Joshua C. Fincke Unknown

Michael Goldstein Computer Science Graduate School, University of Michigan

Ethan D. Gutmann Geology Graduate School, University of Colorado

Josephine W. Hearn American School of Asuncion, Paraguay, Ninth Grade Math Teacher

Tyson L. Jacobs Unknown

Scott A. Kaplan Unknown

Sarah F. Moore Unknown

Daniel W. Nelson Work with Professor Kaplan in Chemistry at Williams College for one year on an NSF CD-ROM project

Snehal R. Patel Unknown

Jonathan R. Putman Unknown

Neelay N. Shah Rotation Engineer for Intel, Portland, Oregon

Daniel E. Sullivan Computer Science Position, Atlanta, GA

Michael B. Sullivan Obtain a position in the web or games industry

Joseph C. Vanderwaart Ph.D. Program in the Department of Computer Science, Carnegie Mellon University

Andrew R. Zimmer Work at the Whitehead Institute on the Human Genome Project