Two of our students, Alice Bernheim and Chris Umans, won prestigious National Science Foundation graduate fellowships. A third senior, Leaf Petersen, received an "honorable mention" from the National Science Foundation. While we must admit that a few other schools (like Harvard and Carnegie-Mellon) produced more winners of National Science Foundation fellowships in computer science than Williams, we must also note that our two fellowship recipients equaled the number of recipients produced in computer science by M.I.T. and Stanford and put us ahead of Yale. Not bad for a class of just fourteen graduates!
Four members of this year's class plan to continue the study of computer science in graduate programs. We were delighted to see that these students were accepted by and will be attending some of the best graduate computer science programs in the country including those at Carnegie Mellon University, the University of California at Berkeley, the University of Washington, and the University of Wisconsin. Other members of the class are going on to employment in positions at large, widely recognized organizations like Microsoft and the Smithsonian Institution and with smaller firms. We wish all our graduates success in the careers they have chosen.
In addition to saying farewell to this year's graduates, we welcome 16 members of the class of `98 as new majors. They join 13 majors from the class of `97. Of course, we expect to be saying wonderful things about these students in the next two years.
One aspect of our program that enables our students to develop their potential as fully as possible while at Williams is the high degree to which we involve students in research through honor theses, independent studies and other special projects. This year's students took great advantage of these opportunities. First, Alice Bernheim, Sarah Calvo, Leaf Petersen, Jasper Rosenberg, Kim Tabtiang (all of the class of `96) and Hank Zill `97 spent the summer of `95 on campus participating in faculty projects in a variety of ways. Their various contributions are described later in this report. Work is just beginning for students, Leaf Petersen `96, Hillary Browne `97 and Geoffrey Hutchison `99, who are joining us this summer: .
During the academic year, Alice Bernheim, Leaf Petersen, Forrest Trepte and Chris Umans pursued research projects culminating in the preparation of honors theses. In addition, several students initiated independent study projects involving advanced topics. Professor Tom Murtagh supervised Sarah Calvo `96 and Kim Tabtiang `96 in a study of implementation techniques for the object-oriented programming language PolyTOIL -- designed by Kim Bruce with the assistance of several students over the last few years. Professor Bruce served as advisor for a group independent study by five Williams students interested in object-oriented analysis and design. The students used the programming language Java to build a very impressive software workbench for computational geometry. Professor Bill Lenhart intends to use and extend the program in order to further his research in computational geometry. Professor Lenhart also supervised Jasper Rosenberg `96 in an independent study looking at advanced topics in Computer Graphics.
Our department upgraded our computing facilities in several major ways during the year. For several years the department has maintained a laboratory of Macintosh computers for students in our introductory courses and a laboratory of Sun Unix workstations for use in advanced courses and research projects. This year we replaced all of the older Motorola 68000 based Macintosh machines with 30 Power Macintosh models.
The change from 68000 based to PowerPC based Macintoshes provided many benefits but required some special efforts. Professor Duane Bailey ported Jabka -- a public domain modeling system developed at Williams by Donald House (currently at Texas A & M) for 68000 based Macintoshes -- to the Power Macintosh. Thanks to Professor Bailey's efforts, the system is the continuing basis for one of our introductory courses, the Art and Science of Computer Graphics. A web gallery of images and movies developed using Jabka by students in Professor Bailey's course can be found at http://www.cs.williams.edu/~bailey/cs109.
In addition to the upgrade of our Macintosh lab, we made some important additions to our Unix systems. Five new Sun workstations were added to our facilities including four SPARCstation 4's and one UltraSPARC workstation. We also added over 10 Gigabytes of disk storage to support the machines in the laboratory.
The department was pleased to participate again in the Class of 1960 Scholars Program. This year, support from this program enabled us to bring Stuart Russell, a distinguished scholar in the field of artificial intelligence, to campus. Professor Russell is a faculty member at the University of California at Berkeley. He has received many honors including a Presidential Young Investigator Award in 1990 and the 1995 IJCAI Computers and Thought Award. Professor Russell gave two talks during his visit to campus. One entitled "Probabilistic Networks vs. Neural Networks," presented work explaining how "learning" could be incorporated into the formalism of probabilistic networks. His other talk, "Rationality and Intelligence," traced the evolution of formal concepts of "intelligence" that underpin practical and theoretical work in the field of artificial intelligence.
During the year, the department experienced several short-term transitions in its faculty associated with sabbatical leaves. Professor Bruce was on leave in the fall, spending 3 months at the Newton Institute for Mathematical Sciences at Cambridge University in England. The special program on the semantics of computation held there during the fall allowed him the opportunity to interact with many researchers in semantics from around the world. During the time in Europe he lectured on types in object-oriented languages at the Newton Institute, Sheffield University, and the Ecole Normale Superieure in Paris. He also presented a paper, "PolyTOIL: A type-safe polymorphic object-oriented language," co-authored with Rob van Gent `93 and Angela Schuett `94, at the 1995 European Conference on Object-Oriented Programming Languages (ECOOP `95) in Aarhus, Denmark in August. This paper was based in part on the students' honors theses. He was also an invited speaker at the Workshop on Advances in Type Systems for Computing in Cambridge, where he discussed a new object-oriented language developed with Leaf Petersen `96.
As the year ends, Professor Tom Murtagh and Professor Bill Lenhart begin sabbatical leaves. Professor Lenhart will be on leave for the fall semester and Professor Murtagh for the full year. Professor Murtagh passes on the role of department chair to Professor Bruce after serving as chair for three years. At the same time, Professor Lenhart passes the responsibility for managing our department's computer facilities to Professor Duane Bailey. To help us through the coming year, Daniel Scharstein will join the department as a Visiting Assistant Professor. Professor Scharstein has just completed his Ph.D. work at Cornell University. His research specialization is in the area of computer vision. He will offer a special, advanced course on computer vision next year.
Professor Duane Bailey continued his work on tools for supporting the parallel programmer. Working with A.J. Bernheim `96, he developed protocols supporting the distribution of shared resources among distributed workstations. The use of these protocols in the tuple-space oriented Linder parallel programming environment give the programmer the flexibility of choosing either distributed or centralized implementations of the tuple-space.
Professor Bailey and A.J. Bernheim also continued the development and implementation of LDB, a set of debugging tools for use with tuple-space based programs. Given the notion that simplicity is important to shortening the startup time, LDB avoids the introduction of complex debugging strategies and techniques that now pervade parallel programming environments. LDB's textual debugging environment provides a suitable set of operators for new parallel programmers. The environment is used in regular offerings of the parallel programming tutorial.
Professor Bailey and Forrest Trepte `96 launched a new line of research involving the compact characterizations of hierarchical aperiodic tilings. The research focuses on implementing abstract data types that support traversals of infinite aperiodic tilings of the line, plane, and three-space. The approach is to develop a generalized specification mechanism for finite sets of prototiles that force non-periodic tiling of space. When the tiling exhibits an invertible inflation property, tiles may be addressed in a way that allows arbitrary, possibly oriented, wanderings through space. A number of new theoretical results about this class of tilings were also developed, including a concise statement of a general local isomorphism theorem. This pretty result suggests that any finite portion of a specific tiling by prototiles appears infinitely often in all other tilings by the same set of tiles.
Bailey and Trepte have used their results to characterize tilings in two and three dimensions including those by Penrose and Danzer. Professor Bailey is currently working on an atlas describing vertex configurations of the Danzer ABCK tiling, and extending results to Socolar's 3-space tiling, as well as Conway and Radin's quaquaversal tiling family.
The goal of Professor Kim Bruce's research is to design languages that are very expressive, yet have a simple conceptual model and make it easier to catch more type errors at compile-time. An important part of the design of these languages involves proving that the type systems are safe; that is, proving that programs that pass the type checker will not have run-time type errors.
During the summer of 1995, Leaf Petersen `96 worked with Professor Bruce in developing a new language, LOOM, which is a modification of the polymorphic object-oriented language PolyTOIL designed over the last few years as part of the senior honors theses of Angela Schuett `93 and Rob van Gent `92. The idea was to simplify the language by removing the subtyping relation from the language in favor of the matching relation, which had been introduced in earlier languages. A key ingredient in the new language was the introduction of a new type constructor, #T, to indicate when values could have any type matching the type T.
Petersen continued this work in his honors thesis during the academic year, designing and implementing a module system to provide support for programming in the large in object-oriented languages. The module system supports separate compilation and provides finer control over information hiding than is available in most object-oriented languages.
Professor Bruce has been very interested in the design of Java, the new object-oriented programming language developed at Sun Microsystems. As mentioned above, he served as advisor for an independent study course in which Java was used in a software engineering project. Professor Bruce also served as a reviewer for the Java Reference Manual that will be published this summer. Professor Bruce has submitted a proposal, based on his research, to Sun for adding polymorphism to Java.
In July of 1995 Professor Bruce was awarded a new 3-year NSF Research Grant totaling $144,433 to study the semantics and design of object-oriented languages. Among other things, this grant will provide funding to hire one or two students each summer to work on the project.
After returning from his leave during the fall semester, Professor Bruce presented lectures at M.I.T., Brown University, Colby College, and Wesleyan University on problems with type systems in object-oriented languages. He also served on a visiting committee in Computer Science at Colby College. Professor Bruce served on the technology advisory committee at the Williamstown Elementary School this year, and was on a search committee for a new computer teacher in the elementary school in the summer of 1995.
Professor Bruce attended the Logic in Computer Science meeting in California in July 1995, as well as the Principles of Programming Languages meeting in January 1996. He served as co-organizer of the Conference on Current Trends in Applied Model Theory in March at the University of Wisconsin in Madison. The conference was in honor of H. J. Keisler, Bruce's Ph.D. thesis advisor.
Assistant Professor Andrea Danyluk continued her research in Artificial Intelligence, specifically on issues arising from the application of Machine Learning to real-world problems. The issues on which she focused this year include the handling of noise in the data used by machine learning algorithms and finding alternative evaluation methods for the output produced by machine learning algorithms. The algorithms studied by Professor Danyluk are primarily inductive learning algorithms that extrapolate general trends from large data sets.
Existing inductive machine learning algorithms generally assume that there is little or no noise in the data from which they attempt to extrapolate general rules or trends. Unfortunately, much of the data available in real corporate databases are notoriously unreliable. As an example, Professor Danyluk has concentrated on data from NYNEX databases. These data describe resolutions to telephone network troubles. If a machine learning algorithm could be successfully applied to these data, the result would be a set of rules for dispatching technicians to troubleshoot customer-reported problems. Anecdotes abound detailing reasons why data entered into this database would not be valid, ranging from sympathy to fear to ignorance to negligence to management pressure. Together with Dr. Foster Provost at NYNEX Science and Technology, Professor Danyluk proposed and implemented four approaches to dealing with data that are not only noisy, but that potentially contain systematic errors. This work was presented at a Workshop on Applying Machine Learning in Practice, which was held in conjunction with the International Machine Learning Conference in July 1995. The paper is entitled "Learning from Bad Data."
Kimberly Tabtiang `96 worked with Professor Danyluk during the summer of 1995. She assisted in running many of the experiments that were reported in "Learning from Bad Data." Kim then started to investigate the effects of different types of data error on inductive machine learning. Together with Professor Danyluk, she itemized types of errors that can occur in data. She then wrote a data generator that could create artificial data sets containing a user-specified list of attributes. These data sets can be used to investigate the effects of erroneous data on the results of inductive machine learning.
This year Professor Danyluk also investigated mechanisms for better evaluating the results of machine learning. The machine learning research community generally judges the performance of a learning algorithm by considering its predictive accuracy on previously unseen data. This is an inadequate measure for many applications. For example, if there are several predictions that might be made by a learning algorithm, and if the cost of making incorrect predictions varies widely, then error cost of predictions might be a better measure than accuracy alone. Together with researchers at NYNEX, Professor Danyluk devised two methods for incorporating error cost, both into learning algorithms and into the evaluation of those algorithms. With Christopher Merz and Michael Pazzani of the University of California at Irvine she wrote "Tuning Numeric Parameters to Troubleshoot a Telephone-Network Loop", which appeared in the February issue of IEEE Expert.
Professor Bill Lenhart pursued his ongoing research in graph theory and computational geometry this past year. His continuing collaboration with Beppe Liotta of Brown University resulted in a paper, "How To Draw Outerplanar Minimum Weight Triangulations", which was presented by Liotta at the international conference Graph Drawing `95, held in September in Passau, Germany. These results were also presented by Professor Lenhart at the Fifth MSI-Stony Brook Workshop on Computational Geometry, held at SUNY Stony Brook in October 1995 and at Brown University in April of 1996. A version of this paper was later published in the March 11, 1996 volume of Information Processing Letters. Lenhart and Liotta are continuing their work on problems involving the study of the combinatorial properties of certain types of graph embeddings called `proximity drawings', most recently focusing their attention on proximity drawings of outerplanar graphs.
This year Professor Lenhart supervised the honors thesis research of Christopher Umans `96. The thesis, titled "An Algorithm For Finding Hamiltonian Cycles In Grid Graphs Without Holes," presented a provably correct efficient algorithm for finding Hamiltonian cycles in a certain class of graphs, and was the culmination of research efforts of other thesis students of Professor Lenhart's over the past few years. Lenhart and Umans will be preparing the thesis for publication this summer. They will also be working together to investigate the possible extension of the methods used in Chris's thesis to larger classes of graphs.
During the summer of 1995, Jasper Rosenberg `96 worked with Professor Lenhart on several problems relating to proximity drawings. One of the results of this collaboration was a program written by Jasper to enumerate all triangulations of a planar point-set using the "reverse-search" technique of Avis and Fukuda.
Professor Tom Murtagh continued work on the design of priority-based collision resolution schemes for contention rings. The objective in this work is to devise ring protocols that provide the low delay at low load associated with contention protocols such as Ethernet and the high throughput associated with token based protocols. In fact, because the protocols Murtagh has designed enable multiple stations to transmit simultaneously, they provide throughput significantly higher than the token ring. Professor Murtagh's work this year was assisted by Sarah Calvo `96 who collected performance data on variations of these protocols by conducting computer simulations of ring networks.
Professor Murtagh also began looking at techniques to implement object-oriented languages in which the rules for determining subtypes are independent of the inheritance mechanism. Using Kim Bruce's PolyTOIL as an example of such a language, Professor Murtagh worked with Kim Tabtiang `96 and Sarah Calvo `96 to develop and implement techniques for object layout that would eliminate the need for dynamic lookups when accessing the instance variables or methods of an object whose actual type might not be known at compile time.
In June of 1995, Professor Murtagh attended the ACM SIGPLAN Programming Language Design and Implementation Conference held as part of the Federated Computing Research Conference.