previousnextTitle Contents


COMPUTER SCIENCE


The 1997-98 academic year once again saw many changes in the department. Visiting Assistant Professor Daniel Scharstein left at the beginning of the year to take a regular position at Middlebury College, while Jay Sachs replaced him in a two year visiting Assistant Professor position. Jay had a special connection to the department even before he arrived, as his thesis advisor at New York University is Benjamin Goldberg, who graduated from Williams in 1982 as a member of the first class of Computer Science graduates here. Professor Tom Murtagh returned from a full-year leave to face a very busy year of course development, while Assistant Professor Andrea Danyluk went off on a well-deserved Assistant Professor leave for the year. Associate Professor Duane Bailey and Professor Kim Bruce will be on leave during 1998-99. As a result, Professor Bill Lenhart will take over the chair duties from Kim. In addition, Visiting Assistant Professor Marton Balazs will join us for the 1998-99 year. Marton is finishing his Ph.D. thesis in Computer Science at W.P.I. (He has already completed a Ph.D. in Mathematics).

Class enrollments in 1997-98 continued their steady increase. Our overall enrollments have increased by 50% over the last four years. We have also had a bumper crop of majors. There are 14 Computer Science majors in the class of 1998, while next year's senior class breaks all past records with 21 majors. While we are thrilled with the increased interest in Computer Science, there have definitely been some growing pains. The advanced elective Computer Networks was originally scheduled to be a tutorial with no more than ten students, but pre-enrollments exceeding 30 resulted in that course being shifted to a regular lecture course. As another example, the new non-majors elective course on the World-Wide Web described below had pre-enrollments that were double what we had expected.

Chris White '00 (left) and Joe Vanderwaart '99 at the Bronfman summer research poster session in the summer of 1998. They are standing in front of posters discussing their work with Professor Kim Bruce on object-oriented language design. The department places a high priority on involving undergraduates with research. Once again we had several students working for the department in the summer. Brendan Burns `98, Mike Ryan `98, Joe Vanderwaart `99, and Ben Chaffee `98 worked for the department in the summer of 1997. The first three served as research assistants, while Ben provided support for our laboratory facilities. Neelay Shah `99, Chris White `00, Joe Vanderwaart `99, and Alfonso Gonzalez del Riego `00 will work for the department during the summer of 1998. The first three will again be research assistants while Alfonso will provide laboratory support. The work of the research assistants is described below in the descriptions of faculty research.

Four students performed honors work this year. Brendan Burns did a thesis on machine learning with Andrea Danyluk, Ben Chaffin `98 and Linden Minnick `98 worked with Duane Bailey on non-periodic tilings, while Jon Burstein's thesis with Kim Bruce was on object-oriented language design and implementation. More detail on their work is provided below.

The Computer Science Department responded to widespread interest in the Internet by introducing a new course this fall, CS 105 The Web: Technologies and Techniques. The course was developed by Tom Murtagh with support from the Mellon Foundation through the Williams Task Force on Computers and the Curriculum. Tom's goal in developing CS 105 was to create a course that simultaneously taught about the fundamentals of digital communications technology and used that technology in pivotal ways as a teaching tool.

The content of the course ranged from practical training in the use of the web as a publishing medium to careful consideration of the technical issues underlying digital communications. The practical training included coverage of HTML, the introduction of image processing software and rudiments of programming in Java. The coverage of digital communication technology ranged from the physics of electromagnetic radiation and the limitations it places on the speed and reliability with which information can be transmitted to the mathematics of public key encryption techniques and the potential such techniques provide for secure and private communications.

In addition to its role as a subject of the course, the Web was used extensively as a medium for the course. All of the course assignments and labs were distributed through the Web. The course lecture notes and most of the readings were also available as Web pages. In addition to text, the course "notes" include several interactive web pages designed to illustrate topics discussed in class. The course was well received, as roughly 100 students requested a place in its first offering, but limited spaces in laboratory sections forced us to cap enrollment at 72. Upper class enrollments for the second offering of the course are currently well over 100 students, with first year students yet to register.

Duane Bailey taught the other non-majors course this year, CS 109, The Art and Science of Computer Graphics. Students again created remarkable images. The on-line gallery of all of the student projects is available at http://www.cs.williams.edu/~cs109.

The department continued integrating the use of the language Java into the departmental curriculum. This was the second year of using Java in CSCI 136, Advanced Programming and Data Structures. This was also the second year of using Duane Bailey's forthcoming text, Java Structures, in the course. Bill Lenhart taught the course in the fall and Kim Bruce in the spring. In both cases, the instructors were able to introduce students to Java's AWT classes to support the use of graphic user interface components as well as to provide some exposure to the use of concurrency with Java's threads. In the second semester, newer compilers allowed us to move to the greatly improved Java 1.1 event model.

Java was also used in several of our more advanced courses, including both Algorithms and Computer Networks. While we are eager to use Java in our regular introductory course, we are being cautious and planning a major revamping of the course to go along with the change in language.

Because of the newness of Java, available compilers are still a bit sluggish. As a result, we will be upgrading our department Macintosh laboratory with new G3-based computers. For at least the first few months of their use they will be among the fastest personal computers available (either Wintel or Macintosh).

As part of the continuing construction of the new science facilities, a major steam line had to be installed through our Macintosh lab in the summer of 1998. As a result, we will be moving our lab to another room in Bronfman. We are eagerly looking forward to the move of the entire department to a renovated Chemistry building in the summer of 2000. This new space will be significantly larger than our current facilities and will be configured to better meet our needs.

During spring break, Duane Bailey constructed a new parallel processor, The Bullpen, configured from 23 recycled 486 and Pentium processors, generously made available by the Office of Information Technology. Students taking the parallel processing course used this new multi-processor for projects in Duane's tutorial in parallel processing. We hope to be able to continuously upgrade this machine as departments and individuals donate increasingly powerful (but seemingly obsolete) hardware. The Bullpen's web site, http://bulldog.cs.williams.edu, provides more details.

At the department's request, the college invited three faculty from outside the college to visit the department and provide an analysis of the department. Professors Scot Drysdale of Dartmouth College, Joe O'Rourke of Smith College, and John Savage of Brown University visited the department during December of 1997. Their report on the department was extremely positive, remarking especially on the quality of the education in Computer Science and the high satisfaction of students. They also provided helpful advice on how to protect faculty time. Two of their most important recommendations were to convert the visiting position that we have been filling for several years into a regular position and to increase the size of the Computer Science faculty. We will be working with the college administration in order to accomplish each of these goals.

Department faculty have continued their involvement with local schools in assisting with computing needs. Kim Bruce and Mary Bailey received certificates of appreciation from the Williamstown Elementary School for their help in setting up a new computing laboratory there. Tom Murtagh continued his involvement in extending and maintaining the computer network at the school. During Winter Study he also brought some students from the web course to the school in order to help terminate connections in order to complete the network. Kim Bruce continued to serve on the Technology Advisory Committee at Mount Greylock High School.

Associate Professor Duane Bailey, Ben Chaffin `98, and Linden Minnick `98 continued investigation of data structures supporting the modeling and traversal of two and three-dimensional aperiodic tilings. Chaffin developed an atlas of 174 local configurations of tiles in the Danzer tiling; previous research had indicated there were only 27. Minnick developed a new continued fractions model for representing distantly forced Penrose tiles, based on an initial specified cluster.

Duane gave talks on this work at Middlebury and Oberlin. While at Oberlin, he also gave the honors exam in Computer Science. Professor Bailey also enjoyed the opportunity to review applications for the national Goldwater Scholarship Committee.

This coming year Duane will be on leave, completing a companion volume Java Elements for his data structures text Java Structures.

Professor Kim Bruce's research on the design of statically-typed object-oriented programming languages included work on improving the design of the new programming language Java as well as continuing the development of the language LOOM, which was designed by Kim and his students. Important features of LOOM include support for parametric polymorphism (type parameters) and a keyword to refer to the type of the object whose method is being executed. These constructs make it much easier for programmers to express their ideas in code while still supporting static type checking.

During the summer of 1997, Joe Vanderwaart `99 worked with Kim on refining the design and implementation of LOOM and Concurrent LOOM, the latter being a concurrent version of LOOM designed by Hilary Browne `97 as part of her honors thesis. In particular, Joe implemented significant extensions to the design of a module system for LOOM that was a part of Leaf Petersen's honors thesis in 1996.

Mike Ryan `98 also worked for Kim investigating the possibility of extending Sun's new object-oriented language Java with the sort of features contained in LOOM. Mike investigated the issue of whether or not to start with a base of Sun's compiler or the Pizza compiler of Odersky and Wadler, and made some initial progress on how the compilers might be modified. Jon Burstein `98 picked up this topic in the fall as part of his senior honors thesis. His thesis included the design and implementation of his "Rupiah" compiler for the extension of Java. Chris White `00 will make further enhancements to the design during the summer of 1998.

Kim also extended his language design work to support inheritance of mutually recursive classes in object-oriented languages. This provides an alternative to Beta's "virtual types," which, while providing great flexibility for the programmer, results in the loss of static type safety -- requiring run-time checks to ensure things don't go wrong. The new construct fits in cleanly with the features introduced in LOOM and retains static type safety. This research resulted in a paper presented in the Fifth International Workshop on Foundations of Object-Oriented Languages, and a more refined paper to be presented in the summer of 1998 in the European Conference on Object-Oriented Languages in Brussels, Belgium. Joe Vanderwaart `99 will again work with Kim this summer on integrating these features in LOOM as well as laying the foundations for an honors thesis next year in the area of programming languages.

Conferences took Kim to Sendai, Japan and Hilton Head, South Carolina in the fall, to San Diego and Atlanta in the winter, and finally to Germany and Belgium in the summer of 1998. Interesting experiences ranged from a traditional Japanese dinner served by geishas in Japan to speaking to architects in Hilton Head. He repeated as co-organizer of the Fifth Workshop on Foundations of Object-Oriented Languages held in San Diego in January, and served as a referee for several conferences and journals. He also served on a visiting committee for the Mathematics and Computer Science Department at Macalester College in Minneapolis, Minnesota, in April. Finally, he co-edited and wrote the editorial for a special issue of the journal Theory and Practice of Object Systems containing papers from the Third Workshop on Foundations of Object-Oriented Languages.

Kim will spend the upcoming fall semester on leave as a visiting Professor at Princeton University where he will be teaching programming languages. He will return to Williamstown in the spring, using the rest of his leave to work on a book on type systems for object-oriented languages.

Assistant Professor Andrea Danyluk enjoyed a year-long leave. During her leave she has been consulting at Bell Atlantic Science and Technology, where she had worked prior to coming to Williams. She has continued her research in Artificial Intelligence (AI), specifically on issues arising from the application of Machine Learning to real-world problems.

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. The specific problem they are addressing is generally termed crisis monitoring -- the ability to detect a critical situation before it occurs. In particular, they are investigating the automatic prediction of T1 failures with significant (multiple days) lead time. Professor Danyluk will chair a workshop on "AI Approaches to Time-series Problems," to be held in conjunction with both the National Conference on AI and the International Machine Learning Conference this summer. Drs. Provost and Fawcett are also members of the organizing committee.

Andrea also continued her research on the application of inductive machine learning. Inductive machine learning algorithms extrapolate general trends from large data sets. While such techniques are most often applied to data in order to induce rules that are not yet known, she demonstrated that they could successfully be applied to "re-learn" previously known information. In particular, she was faced with a multi-person many-month project that involved porting an expert system to a new platform. This expert system was a diagnostic system for customer telephone lines and included a large body of expert-provided information. She showed that inductive learning techniques could be applied to troubles previously diagnosed by the system. The work of translating the expert knowledge for the new system was cut to only a few days.

Among the problems Andrea has been addressing is the issue of how inductive learning algorithms respond when given errorful data -- in particular, data containing systematic errors that may change over time. She has submitted a grant proposal to the National Science Foundation on this topic.

Brendan Burns did an honors thesis this year under the supervision of Professor Danyluk. Brendan investigated the use of Genetic Algorithms to refine expert theories. His algorithm automatically encodes an expert-provided theory as a neural network, and then applies a genetic algorithm to refine the theory to be more consistent with data. He tested his algorithm on three applications from molecular biology: the identification of ribosome binding sites, the identification of promoters in a strand of DNA, and the identification of splice junctions. Brendan expanded on earlier work in this area, using a mutation technique from genetic algorithms that is focused by the expert's knowledge and making bolder changes to the expert knowledge by allowing for the complete deletion of information that is found to be faulty (rather than simply lowering its weight of credibility). He investigated the effects of focusing on information not originally used by the experts versus restructuring the initially provided theory. He will be presenting his work at a poster session at the National Conference on Artificial Intelligence in Madison, WI in July. The poster is entitled "Genetic Search for Accurate Feature Sets." Andrea will present a paper co-authored by Brendan and herself at the Fourth International Workshop on Multistrategy Learning to be held in Italy in June. The title of their paper is "Theory Refinement through Knowledge-Based Feature Set Selection." Brendan began his work with Andrea during the summer of 1997.

Andrea served as a reviewer for the Machine Learning Journal's special issue on Applications.

Bill Lenhart continued to pursue his research in graph theory and computational geometry. Joint work with Christopher Umans `96 resulted in a paper presented at the FOCS `97 conference, held in October at Miami Beach. His continuing collaboration with Beppe Liotta of the University of Rome resulted in a paper "Representable and Forbidden Minimum Weight Triangulations," which was presented at the international conference Graph Drawing `97, held in September at the Third University of Rome. Bill also lectured at McGill University in March on efficient algorithms for finding Hamiltonian cycles in grid graphs.

Bill is currently working on preparing the results of the above-mentioned papers for publication. He continues to investigate the combinatorial properties of certain types of graph embeddings called minimum weight drawings, with the goal of characterizing those graphs admitting such drawings. In addition, he and Chris are continuing to work together on problems related to the Hamiltonicity of various classes of planar graphs.

This past summer Bill was also involved in the workshop "Integrating Recent Research Results, an NSF-CISE Educational Infrastructure Workshop," that took place in July at The Evergreen State College in Olympia, Washington. The goal of the workshop was to bring together undergraduate computer science faculty from colleges throughout the United States with leading researchers in four areas of computer science (software engineering, functional programming, neural networks and computational geometry) to consider how undergraduate computer science curricula might be improved. Bill was one of the three researchers invited to run day-long workshops in computational geometry. His workshop, entitled "Graph Drawing, Geometric Graph Theory and Proximity Drawability," consisted of lectures providing overviews of each of the three areas, along with discussions of how topics from these areas might be incorporated into undergraduate courses in data structure and algorithm design. More information about this workshop is available at http://www.evergreen.edu/user/CISE.

As described earlier, much of Professor Tom Murtagh's time in the last year has been occupied with the development of a new course on the world-wide web and computer networks. More recently, Tom has received additional support from the Mellon Foundation and the New England Consortium on Undergraduate Science Education (NECUSE) to continue the development of the course and the on-line materials associated with it.

The Mellon Foundation and teaching about the Web also occupied Tom's time during the summer of 1997. He served with Ed Epping and Walter Komorowski as an instructor in a program coordinated by the Office of Information Technology that was also funded by the Mellon Foundation. The goal of the program was to train student interns who would assist faculty in projects designed to incorporate the use of digital technology in the curriculum.

During the summer of 1998, Tom began a research project with Neelay Shah `99 on the subject 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. Neelay and Tom will be experimentally measuring the resilience of several proposed watermarking techniques to transformations intended to remove the watermark from the host document.

COMPUTER SCIENCE COLLOQUIA
Marc Blackstein `99, Brendan Burns `98, Ben Chaffin `98, Dan Nelson `99
Williams College
"How I Spent My Summer Vacation"

Jonathan Burstein `98, Dewitt Clinton `98, John Melesky `99, Neelay Shah `99, Joseph Vanderwaart `99

Williams College
"How I Spent My Summer Vacation"

Professor William Lenhart

Williams College
"An Introduction to Graph Drawing"

Computer Science Department Faculty

Williams College
"Graduate School in Computer Science"

Professor Kathryn S. McKinley

Williams College
"An Introduction to Graph Drawing"

Kim B. Bruce

Williams College
"Modules in Object-Oriented Languages"

Professor Robert Cartwright

Rice University and Sun Microsystems Laboratories
"The Quest for Immortal Software"

Kathi Fisler `91

Rice University
"Making a Living Out of CS361: Automata Theory and System Verification"

Lisa Masterman `95

University of Delaware
"ICICLE: Creating an Intelligent Tutoring System for Use as a Writing Tool
by Deaf Users of American Sign Language"

Dr. Philip Wadler

Bell Laboratories and Lucent Technologies
Class of 1960's Scholars Speaker
"From `00 to OO: Millennium Bombs and Java Wars"

Dr. Philip Wadler

Bell Laboratories and Lucent Technologies
Class of 1960's Scholars Speaker
"Pizza to Go, Don't Spill Your Java"

Brendan D. Burns `98

Williams College
"Indigent: Genetically Refining Expert Neural Networks"

Linden Minnick `98

Williams College
"Finding Forced Aperiodic Tiles"

Benjamin J. Chaffin `98

Williams College
"Aperiodic Tiling in Three Dimensions"

Jonathan L. Burstein `98

Williams College
"Rupiah: Yet Another Extended Version of Java"

Dr. Therese C. Biedl

McGill University
"Orthogonal Graph Visualization: The Three-Phase Method With Applications"

Michael Gousie

Rensselaer Polytechnic Institute
"Improving Terrain Reconstruction on a Grid"

Dr. Kevin Atteson

Yale University
"Computational Inversion of Evolution"

Dr. Haney Farid

Massachusetts Institute of Technology
"Digital Image Enhancement"

Computer Science Department

Williams College
"Computer Animation Festival and Department Open House"

Xioguang Wang

University of Massachusetts
"Letting a Computer See More Than a Camera Does"

Dr. Marton E. Balazs

Worcester Polytechnic Institute
"Genetic Algorithms: Evolution-Based Search Methods"

Linden Minnick `98

Williams College
"Generalized Forcing in Aperiodic Tilings"

Brendan D. Burns `98

Williams College
"INDiGENT: Genetically Refining Expert Neural Networks"

Benjamin C. Chaffin `98

Williams College
"Exploring the Danzer Tiling"

Jonathan L. Burstein `98

Williams College
"Rupiah: An Extension to Java Supporting Match-Bounded Parametric Polymorphism,
This Type, and Exact Typing"
OFF-CAMPUS COLLOQUIA
Duane Bailey
"Aperiodic Data Structures"
Department of Mathematics and Computer Science, Middlebury College
"News About Aperiodic Data Structures"
Department of Computer Science, Oberlin College

Kim Bruce

"Modules in Object-Oriented Languages"
Princeton University
"Computer-Aided Instructional Spaces: Here, There, and Everywhere"
Panel at Tradeline Conference on New Facilities Strategies for Colleges,
Universities and Medical Schools, Hilton Head, SC
A Statistically Safe Alternative to Virtual Types"
Fifth International Workshop on Foundations of Object-Oriented Languages (FOOL 5),
San Diego, CA
"Logic in the Computer Science Curriculum"
Panel at SIGCSE `98, Atlanta, GA

Brendan Burns `98 and Andrea Danyluk

"Theory Refinement through Knowledge-Based Feature Set Selection"
International Workshop on Multistrategy Learning, Desenzano del Garda, Italy

Bill Lenhart

"Hamiltonian Cycles in Solid Grid Graphs"
Department of Computer Science, McGill University
POSTGRADUATE PLANS OF COMPUTER SCIENCE MAJORS
Joshua C. Allen:
Developer at the Sabre Group in Burlington, MA
Anthony M. Barnes:
IT Consultant with the administration of colleges and universities for the Exeter Group, Boston, MA
Seth D. Battis:
AP Computer Science Teacher at Baylor School, Chattanooga, Tennessee
Brendan D. Burns:
GTE Laboratories, deferred admission to the University of Wisconsin's Ph.D. Program
Jonathan L. Burstein:
Developer, Windows User Interface at Microsoft Corporation
Benjamin C. Chaffin:
Rotation Engineer at Intel, Portland, Oregon
Charles M. Chen:
Unknown
DeWitt Clinton, Jr.:
Program Developer in the Developer Tools Division of Microsoft
Mimi Y. Huang.:
Unknown
Eping E. Hung:
Software Engineer, Employease, Atlanta, GA
Joshua M. Mankoff:
IT Consultant with the administration of colleges and universities for the Exeter Group, Boston, MA
Linden Minnick:
Rotation Engineer for Intel, Portland, Oregon
Michael Ryan:
Real Estate Investment Banking analyst at Merrill Lynch, Manhattan, NY
Derek Sasaki-Scanlon:
Internet Services Developer for Comstock, Inc., New York City, NY


previousnextTitle Contents