The Computer Science Department experienced another year of major and minor transitions within our faculty. The highlight of these transitions was the promotion of Professor Duane Bailey to the rank of Associate Professor effective July, 1, 1995. Duane has contributed energetically to the department in many ways since his arrival. We are delighted that he will continue as a tenured member of our faculty.
Even before his promotion was announced, the department gave Duane a new chance to "contribute energetically" by asking him to serve as the department's faculty facilities manager for the year. During the year, Duane has worked hard to manage the installation of upgrades to the hardware and software used in the department's Sun and Macintosh computing laboratories. As a result of his efforts, these laboratories continue to provide an excellent environment for computing associated with our teaching and research efforts.
In taking on the lab position, Duane relieved Professor Tom Murtagh, who had served in that position for the last three years. Tom's relief was brief, however, as he moved on to new administrative duties as department chair. The real relief went to Professor Kim Bruce who stepped down as chair at the beginning of the year.
The department welcomed Matthew Merzbacher as a Visiting Assistant Professor for the year. Matthew came to us from UCLA where he had just completed a Ph.D. in Computer Science. His specialty is the application of Artificial Intelligence to databases. Matthew will begin a position in the Computer Science Department at Wellesley College in the fall of 1994. During the year, Matthew offered a wide range of courses from a non-majors course on computer graphics to an elective on artificial intelligence.
Next fall, our department will be joined by a new Assistant Professor, Andrea Danyluk. Andrea was actually hired in the spring of 1993, but deferred her arrival at Williams one year to ease her transition. She is currently working as the project leader of the Adaptive Expert Systems Project at NYNEX Science and Technology, Inc. Her specialty is Artificial Intelligence, especially the design and application of expert systems.
Along with the somewhat unpredictable faculty transitions, our department experienced some very predictable student transitions. Six seniors graduated as Computer Science majors and we were joined by thirteen talented new sophomore majors.
Like many of our recent majors, most of this year's seniors became involved in Computer Science research projects and most of them will go on to more advanced studies in Computer Science in graduate school. Three of our six seniors completed honors theses. Four of the six will be entering graduate programs in Computer Science next year at the University of California at Berkeley, the University of Washington and the University of Maryland. A fifth senior, Marina Yeroulanou, will enter a graduate program in Archaeology at Oxford.
Our seniors received several special awards. Angela Schuett '94 was granted a fellowship for graduate study by the National Physical Sciences Consortium. This fellowship will provide up to $180,000 in support for Angela's graduate studies over six years. Daniel Fasulo '94 was selected as an ARCS scholar by the Massachusetts chapter of the ARCS foundation (Achievement Rewards for College Scientists.) Daniel received a $5000 scholarship toward his studies at Williams as part of this award. Natasha Rose '94 was chosen by the CRA (Computing Research Association) to participate in the CRA Distributed Mentor Program. This program provides support for Natasha to spend the summer working as a research assistant for Professor Susan Rodgers in the Computer Science Department at Rensselaer Polytechnic Institute.
We were particularly pleased that one of our new sophomore majors was also selected to participate in the CRA Distributed Mentor program. A.J. Bernheim '96 will spend the summer at the University of Oregon working on problems involving parallel computation with Professor Janice Cuny.
As in the other science programs at Williams, such summer opportunities play a critical role in involving students in research. During the summer of 1993, seven students worked for members of the Computer Science Department in various capacities. Dan Fasulo '94, Stephan Fiedler '93, Sean Sandys '94 and Angela Schuett '94 worked as research assistants. Keith Long '95 and Ben Whaley '93 assisted Professor Kim Bruce with the development of curricular materials for a new course, CSCI 137. Stina Bridgeman '95 worked as laboratory assistant on the departmental computing facilities of Sun workstations and Apple Macintosh computers.
Student assistants for the summer of 1994 are just beginning their work. Dan Fasulo '94, Stina Bridgeman '95, Stephen McLaughry '95, Leaf Petersen '96 and Jasper Rosenberg '96 are working as summer research assistants. Kimberly Tabtiang '96 is working as our laboratory assistant.
The most significant curricular development in the department was the initiation of a pair of experiments in alternative approaches to our second semester introductory course, CSCI 136: Data Structures and Advanced Programming. In the fall, Professor Kim Bruce introduced CSCI 137: Programming Paradigms and Data Structures. as an alternative to CSCI 136. This new course presented an unusual introduction to data structures using a combination of a functional programming language, ML, to introduce the idea of prototyping and using abstract data types, and an object- oriented language, Object Pascal, to introduce ideas of efficient implementation and reuse of data structures. As mentioned above, Ben Whaley '93 and Stephan Fiedler '93 worked for Professor Bruce during the summer developing software for this course. In the spring, Professor Duane Bailey significantly revised the existing CSCI 136 course. In addition to changing the material covered in class to include more analysis of algorithms, Duane switched from using Modula-2 to C++ as the vehicle for laboratory assignments associated with the course.
Another important addition to our curriculum was a new Winter Study course: CSCI 012: Databases: Making Order Out of Chaos. This course was offered by Shahram Amiri, the College's Executive Director of Information Technology. In the course, students learned about factors to consider in designing a database, including query languages, processing, and optimization as they impact issues such as the user-interface and database security.
The department was pleased to participate in the Class of 1960 scholars program for the second year. This year, support from this program enabled us to bring Professor Jeannette Wing of Carnegie- Mellon University to the Williams campus for several days. Professor Wing gave two talks on her work toward the development of LARCH, a program specification language and met with students in several less formal settings.
Professor Duane Bailey continued his investigation of dynamically structured parallel programs with Sean Sandys '94, an Andrew T. Mellon Fellow. This work resulted in Sean's thesis entitled "Support for Dynamic Itinerary-Based Communication". Research with Sandys has resulted in extensions to a parallel programming environment that allows programmers to describe programs whose topology changes with time or algorithmic progress.
Duane has been elected Vice Chairman of the Mathematics and Computer Science Division of the Council on Undergraduate Research, and is an Associate Editor for their debut edition of the Directory of Undergraduate Programs in Mathematics and Computer Science.
Professor Bailey was the spring Sigma Xi speaker, presenting lectures on "Growing Massively Parallel Programs" and "Supporting Patterned Communication in Parallel Programs".
Professor Bailey attended the DIMACS Conference on Parallel Algorithms in May at Princeton. He will give a talk entitled "Developing Research Skills Within the Curriculum" at the Fifth National CUR Conference on Undergraduate Research at Bates College in June.
Professor Kim Bruce continued to pursue his research on the semantics and design of object- oriented programming languages. The goal is to design and implement object-oriented languages which are guaranteed to catch type errors at compile-time. The focus this year was to extend the power of these languages by addressing the issue of parametric polymorphism, the ability to pass types as parameters in functions. The original prototype functional, object-oriented language, TOOPLE (for Typed Object-Oriented Programming Language), has now been superseded by TOIL (for Typed Object-Oriented Imperative Language), which was designed with Rob van Gent '93 as part of his honors thesis.
Picking up where Rob left off in the spring, Angela Schuett '94 began work in the summer of 1993 in cleaning up and extending TOIL. After simplifying some of the TOIL constructs, Angie began designing an extension, PolyTOIL, which would add the capability of using parametric polymorphism to TOIL. This project was successfully completed in Angie's senior honors thesis. While further work needs to be done in cleaning up the language design and proving that the language has nice theoretical properties, a PolyTOIL interpreter has been successfully implemented in ML. Leaf Petersen '96 and Jasper Rosenberg '96 will be working with Professor Bruce in the summer of 1994 in further developing PolyTOIL.
A paper on TOOPLE (a functional predecessor of TOIL), co-authored by Bruce, Tom Murtagh, Jon Crabtree '93, Rob van Gent '93, and two Harvard University researchers, was presented in September at the 1993 Object-Oriented Programming, Systems, and Applications (OOPSLA) conference in Washington, D It was entitled "Safe and Decidable Type Checking in an Object Oriented Language", and presented an algorithm which established that type-checking was decidable for TOOPLE (and hence TOIL, as well).
In October, Bruce organized and co-chaired an NSF and ESPRIT-sponsored International Workshop on the Foundations of Object-Oriented Programming Languages at Stanford University. Rob van Gent '93, currently a Computer Science graduate student at Stanford, gave a talk on TOIL. A report on the workshop was published in the March, 1994 issue of the SIGPLAN Notices.
In January, Bruce chaired a panel following a tutorial session at the 1994 ACM Symposium on Principles of Programming Languages, in Portland, Oregon. The panel discussed language design issues related to object-oriented programming languages.
In March he gave a paper and participated in a panel discussion at the 1994 ACM Symposium on Computer Science Education in Phoenix, Arizona. His paper, "Attracting (& Keeping) the Best and the Brightest: An Entry-Level Course for Experienced Introductory Students" described the innovations in Computer Science 135, a Ford Foundation-sponsored course which included an introduction to functional programming languages and experimental architectures for highly- parallel computers. In the panel, "Describing the CS Forest to Undergraduates," he presented views developed by the Williams CS department on the best ways to introduce introductory students to advanced topics in Computer Science.
In January, ignoring inter-campus rivalries, Professor Bruce served on a visiting committee for Computer Science at Amherst College. He was also a freshman advisor this year, served as a program committee member for OOPSLA '94, served as an outside reader for a Ph.D. thesis at the Ecole Normale Supérieure in Paris, and refereed papers and grant proposals. He was named to the Editorial Board of the new journal, Theory and Practice of Object Systems (TAPOS). He also attended a meeting of the North American Types Jumelage at SRI in Menlo Park, California, and of the Liberal Arts Computer Science Consortium at Swarthmore College.
In his spare time he helped obtain old microcomputers from Williams for the computing laboratory at the Williamstown Elementary School, while teaching a few sessions on computing to 3rd graders in the fall.
Professor William Lenhart was a co-author on two papers presented at the workshop Graph Drawing '93: the ALCOM International Workshop on Graph Drawing and Topological Graph Algorithms. The first, entitled "Characterizing Proximity Trees", was written jointly with Prosenjit Bose and Giuseppe Liotta. The second paper, "Dominance Drawings of Bipartite Graphs" was completed with Peter Eades, Hossam ElGindy, Michael Houle, Mirka Miller, David Rappaport and Sue Whitesides. A version of the first paper was also accepted for publication in a special issue of the journal Algorithmica devoted to Graph Drawing.
In November, Professor Lenhart gave a lecture entitled "Recognizing Proximity Graphs" at the Department of Mathematics and Computer Science of the University of Quebec at Montreal. In August of '93 he attended the 3rd Workshop on Algorithms and Data Structures (WADS '93) conference in Montreal, for which he also served as a referee.
This summer, Professor Lenhart has been invited to spend a month as a visiting professor in the Computer Science Department of the University of Rome.
Professor Thomas Murtagh continued work on protocols for high speed networks which he began last year with the assistance of Dan Yu '93. This year he worked with Matt Schroth '95 to design and implement a simulator to be used to predict the performance of members of the family of protocols he and Dan had proposed.
Professor Murtagh also resumed his work on the implementation of programming languages. He worked with Daniel Fasulo '94 on the problem of assigning registers to the parameters of functions in a way that reduces the overhead associated with function invocation. Together they developed a new heuristic for register assignment. This summer, they are completing the implementation of a prototype compiler to evaluate the effectiveness of their techniques.
As mentioned above, Professor Murtagh was a co-author on a paper describing work done with Professor Bruce on the programming language TOOPLE. He also attended the 1994 ACM Conference on Lisp and Functional Programming in June.