<< >> Title Contents

COMPUTER SCIENCE DEPARTMENT


The 1996-97 academic year was one of changes for the department as we saw two members of the department go on leave, welcomed new staff and visitors, introduced and revised several courses in interesting ways, and watched our course enrollments and majors continue to increase. While we did not realize it at the outset, it also turned out to have been the beginning of a department-wide exploration of the uses the language Java and the World Wide Web in our curriculum.

Professor Tom Murtagh stepped down as department chair to begin a year-long sabbatical leave, and Professor Bill Lenhart enjoyed a semester-long leave this past fall. We were very pleased to have Daniel Scharstein join us as a visiting assistant professor to help fill in for Tom and Bill. Daniel, who is originally from Germany, finished his Ph.D. at Cornell University with a specialty in computer vision. We took advantage of Daniel's expertise to introduce a new tutorial in computer vision in the spring term. Professor Adrian Fiech of Memorial University in St. Johns, Newfoundland also joined the department in the fall as a visiting researcher. He worked with Professor Kim Bruce on research in the design of type-safe object-oriented programming languages. Professor Bruce was also pressed into service once more as department chair.

We were delighted to welcome Mary Bailey to the department to provide computer systems support. This is a new full-time position which replaced the half-time Facilities Manager position formerly held by Adrian Alcala, who has returned to full-time consulting. Mary has already shown herself to be invaluable to the department in keeping the computer systems going through thick and thin.

We are tempted to call the 1996-97 academic year the "Year of Java and the Web" in our department. While members of the department had been active in creating web pages for their courses and research, this was the first year that Java and the World Wide Web had a major impact on courses in the department.

Professor Duane Bailey started us off in the fall by changing the language used in the data structures course, CSCI 136, over to the new object-oriented language, Java. In association with this change, he developed an extensive data structures library implemented in Java, and wrote an accompanying data structures text book. The text was class-tested in the fall and spring here, and will be published this summer. Professor Kim Bruce followed Duane's lead with Java in the data structures course in the spring, adding a greater emphasis on the use of the Java AWT to build graphic user interfaces. This allowed students to build more interactive applications and web-based applets. Java also provided support for introducing students to concurrent programming in this course.

Professor Bill Lenhart joined in by shifting the language used in the Computer Graphics course this spring from C++ to Java. While this shift required an enormous effort on his part to port software libraries to Java, he reported that it paid off in a big way, enabling students to develop more interesting graphics projects with much greater ease than in the past.

Professor Daniel Scharstein introduced a new Winter Study course on publishing and programming on the World-Wide Web, including some use of Java. The overwhelming student interest in this course helped motivate Professor Murtagh to design a new regular course aimed at non-majors for the fall of 1997 which examines the technology behind the world-wide web. While students will learn how to make web pages and a bit of programming in Java, most of the focus of the course will be on understanding how networks, data compression, and generalized mark-up languages work to make the World Wide Web possible.

We had another strong group of student majors this year, with 13 seniors and 17 juniors. The sophomore class set a new high mark this spring with 20 students signing up to be Computer Science majors. While in the past a number of our students went directly on to graduate school, this year, perhaps in part because of the booming job market for computer science graduates, all but one of our majors are directly entering the job market. Their employers are listed at the end of this section. The one student continuing directly to graduate school is Dan Norcross `97, who will be studying Asian Studies at Harvard in the fall.

As is traditional, many of our students participated in independent research or study during the academic year. Two seniors did honors theses this year. Hilary Browne worked under the supervision of Professor Kim Bruce on the design and implementation of a concurrent object-oriented programming language, while Jeff Bolas worked under the supervision of Professor Andrea Danyluk on the design of a system to learn and predict users' interests in the content of World Wide Web pages. Several students were also involved in independent study courses. In the fall, Beverly Richardson `97 worked on topics in machine learning with Professor Danyluk, while Max Ross `97 studied database design under the guidance of Professor Bruce. In the spring, Ben Chaffin `98 studied computer architecture under the guidance of Professor Bailey, while Dan Norcross `97 worked with Professors Bruce and Murtagh on a source-to-source transformer to translate programs in the object-oriented language LOOM to Java.

During the summer of 1996, Hilary Browne `97 and Leaf Petersen `96 worked for Professor Bruce on refining the implementation of the programming language LOOM, which had been the topic of Leaf's honors thesis. Geoff Hutchinson `98 also worked for the department that summer in providing support for the department laboratory of Sun workstations. During the academic year, Kim Tabtiang `96, who was working at Williams for a year before attending graduate school at the University of Wisconsin, worked for Professors Bailey and Bruce in studying Java's capabilities and assisting in the design of Java graphics and data structure libraries. During the summer of 1997, Ben Chaffin `98 will provide support for the department Sun lab, Brendan Burns `98 will work for Professor Danyluk in machine learning, Joe Vanderwaart `99 will work with Professor Bruce on the design and implementation of object-oriented languages, and Mike Ryan `98 will work with Professors Bruce and Murtagh on implementing an extension of Java that supports classes with type parameters.

Having mentioned Professor Scharstein's course on the World Wide Web earlier, we cannot resist describing our other Winter Study course for 1997, a course in computer animation taught by Jeff Kleiser. Jeff is one of the principals of the Kleiser-Walczak Construction Company, a firm based in North Adams that specializes in computer animation for movies. If you have watched the special effects in movies like Stargate or Judge Dredd, you have seen their work. This past January, Kleiser worked with 12 Williams students using the company's state of the art graphics hardware and software to create a one minute video commercial for Williams College. As one might expect from Jeff's background, this was not a commercial for the Williams of today. Instead it depicted a Williams College of the future with a fully robotic faculty! The video has been a huge hit with students and alumni who have seen it. Luckily Jeff will be back next year to offer a repeat of the course. We can't wait to see what his students will come up with!

The department also had a number of interesting colloquia this year, whose titles are listed at the end of this section. The Class of 60's Scholars' fund supported the visits of Professor Dean Pomerleau `85 in the fall and Professor Lynn Andrea Stein in the spring. Professor Pomerleau, now at Carnegie-Mellon University, fascinated the audience with description of his "No Hands Across America" project in which he and one of his graduate students rode cross country in a mini-van in which the steering was controlled by a lap-top computer. Professor Stein lectured on innovations in computer science education, focusing on the use of Java as a tool for teaching interaction and concurrency in introductory computer science courses.

Faculty and staff in the department were involved in several outreach programs this year in the local public schools. After helping convince Williams to provide an Internet link to Williamstown Elementary School, department members Mary Bailey, Duane Bailey (and indeed the whole Bailey clan), Tom Murtagh, and Kim Bruce helped with networking much of the school as part of Massachusetts Net Day in the fall. Murtagh also spent many hours in the school in the spring, terminating cables, configuring hardware and software, and generally extending the school network. Bruce served again this year on the technology advisory committees of both the elementary school and Mt. Greylock High School, while Murtagh served on a hiring committee for a math teacher at Mt. Greylock.

There will be a few personnel changes in the department next year. Professor Andrea Danyluk, who was recently reappointed to another four-year term as Assistant Professor, will be on leave all of next year. During her leave she will be a consultant for NYNEX Science and Technology, where she was employed before coming to Williams. Helping out for the next two years will be Visiting Assistant Professor Jay Sachs, who just finished his Ph.D. thesis in programming languages at New York University. Interestingly, Jay's thesis advisor was Professor Benjamin Goldberg `82, a member of the first Williams graduating class to have an opportunity to specialize in computer science.

Associate Professor Duane Bailey spent most of the year completing a manuscript for teaching data structures using the Java programming language, and implementing the extensive data structures library which accompanies the course. He course-tested the text this past fall in our department's data structures course, and it was used again this spring by Professor Bruce. Java is a modern, object-oriented language designed especially for use with the web. The library of data structures described in the text is freely available on the Web, for educational use. Duane's book, Java Structures: Data Structures in Java for the Principled Programmer will be published by McGraw-Hill/Irwin later this fall. Duane also supervised Ben Chaffin `98 in an independent study course on computer architecture's this spring.

Professor Kim Bruce continued his research on the design of statically-typed object-oriented programming languages. During the summer of 1996, Leaf Petersen `96 and Hilary Browne `97 worked for Kim in enhancing and cleaning up the interpreter for the language LOOM, which was designed by Kim and Leaf during the summer of `95, and extended with modules by Leaf as part of his senior honors thesis. LOOM is based on the language PolyTOIL, a statically-typed object-oriented language with strong support for polymorphism, which was designed earlier by Kim and two previous honors students, Rob van Gent `94 and Angela Schuett `95. LOOM is distinguished by replacing all uses of subtyping by a newer, more general relation known as "matching." This replacement allows great simplification of the language, while retaining the language's rich expressiveness.

During Professor Adrian Fiech's visit in the fall semester, Kim and Adrian were able to rework and simplify the proofs of type-correctness for both PolyTOIL and LOOM. A paper, "Subtyping Is Not a Good `Match' for Object-Oriented Languages," based on Leaf Petersen's thesis and the subsequent proof of its type-safety, was presented at the International Workshop of Foundations of Object-Oriented Languages (FOOL 4) in Paris in January, and at the European Conference on Object-Oriented Programming (ECOOP `97) in Finland in June, 1997.

Hilary Browne's honors thesis, produced under Kim's guidance, involved adding features supporting concurrency to LOOM. While object-oriented languages provide many features that provide strong support for the construction of programs, programming computers with many processes running concurrently has been notoriously error prone and difficult. Hilary's goal was to design easy to use features that would integrate well with the object-oriented features of LOOM. Her thesis included the design and implementation of a new language, Concurrent LOOM. While there are still a few features that Kim and Hilary would like to add to the language, they expect Concurrent LOOM to provide an easy transition for object-oriented programmers wishing to write reliable programs for computers with multiple processors. Joe Vandervaart `99 will work with Kim this summer on further enhancements to the languages and their interpreters.

The new Java programming language was the focus of attention both in Professor Bruce's teaching and in his research. As mentioned earlier, both he and Duane Bailey used Java in the Data Structures course (CSCI 136) this year. While both found Java to be a significant improvement over the use of C++, certain limitations of Java proved to be particularly awkward. These involved the lack of support for parameterized classes and the resulting proliferation of type casts in Java classes.

These problems inspired Professors Bruce and Murtagh to start a new project involving the creation of an enhanced Java. The first stage of this project involved working with Dan Norcross `97 this spring in writing a LOOM to Java translator in order to determine how feasible it would be to add polymorphism and a "This Type" construct to Java. The next phase of this project will be carried out this summer with Michael Ryan `98. The goal is to modify Sun's Java compiler to support extensions to the Java syntax that allow the expression and use of polymorphism.

Professor Bruce was involved with several conferences and workshops over the last year. In June, 1996, he participated in the conference on Strategic Directions in Computer Science, serving on special working groups in Programming Languages and Computer Science Education. These groups published a report on their deliberations in the December, 1996, issue of ACM Computing Surveys. Professor Bruce also contributed to the design of a new model curriculum for computer science in liberal arts colleges. The report on this design was published in the Communications of ACM in December, 1996.

Professor Bruce presented a 3 hour tutorial entitled "Static Typing in Object-Oriented Languages: Achieving Expressiveness and Safety" at the ECOOP `96 meeting in Linz, Austria in August `96. He repeated this tutorial at the OOPSLA `96 meeting in San Jose, California, in September, and again at the University of Massachusetts, Amherst, in December. He also gave a talk, "Designing Provably Safe and Flexible Object-Oriented Languages," at the University of Massachusetts.

Professor Bruce served as co-organizer of two meetings of the International Workshop on Foundations of Object-Oriented Languages (FOOL) during the last 12 months. He also served as program committee chair for the first of these, FOOL 3, held in New Brunswick, New Jersey, in July. Leaf Petersen `96 and Hilary Browne `97 also attended that workshop and assisted with the running of the meeting. While in New Jersey for the FOOL 3 workshop, Professor Bruce also served on a panel on "Teaching Logic in Computer Science" that was part of the Workshop on Teaching Logic and Reasoning in an Illogical World, and attended the Logic in Computer Science conference. Finally he served on the program committee of ASIAN `96, held in Singapore (though unfortunately was not able to attend the conference).

Professor Bruce served as advisor for Programming Languages for the CRC Handbook for Computer Science and Engineering that was published in 1997. Aside from recruiting authors and editing articles on programming languages for that volume, he also co-authored an article for the handbook on imperative programming languages. Finally, he was named a "Golden Core Member" of the IEEE Computer Society for his contributions to the development of computer science curricula.

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 alternative evaluation metrics for inductive machine learning algorithms. Inductive machine learning algorithms extrapolate general trends from large data sets.

In inducing general trends (or rules) from large data sets, accuracy is most often taken to be the goal. That is, the rules or trends found in the data should predict previously unseen data accurately. While this goal is completely reasonable, it is generally the case that the rules extrapolated from a data set will not be 100% accurate. In many cases, the accuracy is significantly lower. Given the assumption that all inductive learning methods will produce results with some level of inaccuracy, it becomes important to analyze the situations in which the algorithm fails. For example, say that an inductive algorithm is applied to a data set of cancer patient histories in order to extrapolate rules that help to predict cases in which a patient has been treated for cancer with an apparent cure, but will have a reoccurrence of the disease. While it might be acceptable to falsely predict that a patient will have a reoccurrence of cancer, it may be completely unacceptable to falsely predict that a patient has been cured. The former might result in unnecessary treatment. The latter would likely result in death. There are clearly costs associated with both outcomes. A set of rules that incorrectly predicts even a small percentage of cases (say 1 or 2%) might result in unacceptable cost. It is critical in many applications to take cost into account as the primary measure of success. This requires not only that results of machine learning be measured differently, but that alternative goals be used to motivate the rules and trends extrapolated by the algorithms. Together with Dr. Foster Provost from NYNEX Science and Technology, Professor Danyluk implemented a cost-sensitive learning algorithm, that has been successfully tested on a real application. The algorithm and results are presented in a paper entitled "A Study of Real-world Metrics for Data Mining/Machine Learning" that has been submitted to the journal Informatica.

This year Professor Danyluk also began working on a new line of research, together with her honors thesis student, Jeff Bolas `97. Jeff was interested in the growth of the World Wide Web, and more specifically, the difficulty of finding documents that are useful or interesting. A combination of information retrieval and machine learning techniques have been applied to "watch over" users and build profiles that capture users' interests. Many of these techniques, which rank documents on a scale of interest to a user, analyze those documents by considering the words of which they are composed. Jeff began an investigation of a hypothesis that "higher level" linguistic structures would provide more useful information than individual words.

Brendan Burns `98 will begin work with Professor Danyluk this summer and will continue as her honors thesis student during the next academic year.

In addition to her teaching and research, Andrea gave a talk at Vassar College on the history and future of machine learning. She also continued her work as a reviewer for the Machine Learning Journal.

Bill Lenhart enjoyed a one-semester sabbatical this fall, pursuing his research in graph theory and computational geometry. His continuing collaboration with Beppe Liotta of the University of Rome resulted in a paper "Proximity Drawings of Outerplanar Graphs," which was presented at the international conference Graph Drawing `96, held in September at the Mathematical Sciences Research Institute at Berkeley. Bill also gave lectures at the University of Rome in December and at the Université de Québec à Montréal in March on efficient algorithms for producing "minimum weight" drawings of maximal outerplanar graphs. He is continuing 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.

This year Bill continued to work with Christopher Umans `96, currently a graduate student in computer science at Berkeley, on generalizing the results obtained in Chris's honors thesis. The work involves the design of an efficient algorithm for finding hamiltonian cycles in a certain class of planar graphs. This year they were able to extend their results to encompass a much larger class of graphs. They have submitted their work for inclusion in the next Foundations of Computer Science conference, and plan to publish these results later this year.

The remainder of Bill's sabbatical leave was spent developing the expertise and software necessary for revamping the department's computer graphics course for majors. The course is now being taught using the Java programming language, a modern object-oriented language. Students were able to work on the machine of their choice anywhere on campus and could access documentation and other course materials easily over the campus network using their favorite web browser. The change to Java also allowed students to develop more complex graphics systems with greater ease.

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. Over the past few years, Professor Murtagh and his students have devised a protocol that appears to outperform existing alternatives. This year, work on this project has been focused on gathering data about the performance of this protocol by perfecting a simulator for the system.

Professor Murtagh also continued working with Kim Bruce on implementation issues raised by Kim's proposals for the design of object-oriented languages. They have looked at the possibility of adding extensions based on Kim's work to the Java language and at implementations based on the Java Virtual Machine.

Professor Murtagh also devoted considerable time to curricular design efforts intended to incorporate the use of the Java language into our program. He was awarded funding from the college's grant from the Mellon Foundation to develop a non-majors course, The Web: Technologies and Techniques, in the fall of 1997. He will also be involved in the summer of 1997 with a program arranged by the Center for Computing to teach a number of student workers to become relatively expert in design of World Wide Web sites.

In June of 1996, Professor Murtagh attended the ACM SIGPLAN Programming Language Design and Implementation Conference.

Visiting Assistant Professor Daniel Scharstein joined the department for the full academic year. Daniel received his Ph.D. from Cornell University in January 1997. His thesis, entitled "View Synthesis Using Stereo Vision," was recently accepted for publication in the Springer-Verlag Lecture Notes in Computer Science series.

In June of 1996, Professor Scharstein presented two papers at the IEEE Conference on Computer Vision and Pattern Recognition in San Francisco. One of these papers, entitled "Stereo Matching with Non-Linear Diffusion" (joint work with Dr. Richard Szeliski at Microsoft Research), has been accepted for publication in the International Journal of Computer Vision. In June 1997, he attended the IEEE Conference on Computer Vision and Pattern Recognition in San Juan, Puerto Rico.

Professor Scharstein gave two talks in Williams' Computer Science Colloquia: "Making Computers See: An Overview of Computer Vision" in October 1996, and "A Chip That Plays NIM" in May 1997. The latter talk was also given at Middlebury College in February 1997. He also gave a talk on his thesis research at Williams' Bronfman Science Center lunch series in March 1997.

Professor Scharstein developed and taught two new courses at Williams. The first course, a Winter Study Project on publishing and programming on the World Wide Web, taught students how to develop web pages with simple interactive elements using Java. The second course was an introduction to computer vision aimed at juniors and seniors. Final programming projects completed by students in this class included a jigsaw puzzle solver, a face recognition system, and a rendering system for 3D models computed from 2D images.

Professor Scharstein has accepted a tenure-track appointment at Middlebury College starting in the fall of 1997. Both he and the department are looking forward to continued close contact in the coming years..

COMPUTER SCIENCE COLLOQUIA
Jeffrey G. Bolas `97, Hilary K. Browne `97, Max C. Ross `97, Andrew Schein `97
Williams College
"Computer Science Majors Talk About Their Summer Work Experiences, Part I"
Benjamin C. Chaffin `98, Laird E. Dornin `97, Beverly J. Richardson `97, Iein Valdez `97
Williams College
"Computer Science Majors Talk About Their Summer Work Experiences, Part II"
A Discussion Led by the Computer Science Department Faculty, Williams College
"Graduate School in Computer Science"
Dr. Daniel Scharstein, Williams College
"Making Computers See: An Overview of Computer Vision"
Dr. Matthew L. Ginsberg, CIRL, University of Oregon
"Carbon vs. Silicon: Will Machines Ever Think Like We Do?"
Dr. Moshe Y. Vardi, Rice University
"Program Verification: A Dream Comes True"
Dr. Dexter Kozen, Cornell University
"Kleene Algebra with Tests and Commutativity Conditions"
Dr. Dean Pomerleau, Carnegie Mellon University
Class of 1960's Scholars Speaker
"No Hands Across America: A Chronicle of Recent Progress in Robot Vehicles"
Stephen Springer, NYNEX Science and Technology, Inc.
"Issues in Developing Speech and Language Interfaces"
The Computer Science Faculty, Williams College
"Research in Computer Science"
Hilary K. Browne, Williams College
"Adding Concurrency (and Water) to LOOM"
Jeffrey G. Bolas, Williams College
"Natural Language Preprocessing In Filtering Techniques, or The Gospel According to Phil-Tor"
Dr. Stephen Blythe, Rensselaer Polytechnic Institute
"Design Space Exploration in High-Level Synthesis"
Dr. Jay Sachs, New York University
"Polymorphic Modules for Object-Oriented Programming"
Dr. Lynn Andrea Stein, Artificial Intelligence Laboratory, Massachusetts Institute of Technology
Class of 1960's Scholars Speaker
"Changing Conceptions of Computation: Pedagogic Implications"
Dr. Daniel Scharstein, Williams College
"A Chip That Plays NIM"
The 1997 Computer Graphics Video Festival
POSTGRADUATE PLANS OF DEPARTMENT MAJORS
Jeffrey G. Bolas:
Kenan Systems Corporation, Cambridge, MA, Consultant of On-line Analytical Processing Applications
Hilary K. Browne:
GTE Labs, Waltham, MA, in the Service Concept Design Department as a Technical Staff member
Sarah B. Cottay:
Anderson Consulting, Technology Park, Northbrook, Illinois
Laird E. Dornin:
Hewlett Packard, Chelmsford, MA, Software Engineer in the Net Technologies Lab
Noah M. Harlan:
Coordinating Producer of the soap opera "Guiding Light"
Derek A. Hays:
Metrica, Inc., Winchester, MA, Applications Engineer
Daniel A. Norcross:
Entering Harvard in the Department of East Asian Regional Studies to pursue a graduate degree in Asian Studies
Beverly J. Richardson:
Foree Consulting, Austin, TX which does business consulting and creates custom applications using Lotus Notes
Max C. Ross:
PTCG, Boston, MA, a subsidiary of American Airlines, writing logistics software for the transportation industry
Andrew I. Schein:
Employease, Williamstown, MA, which provides benefits management over the Internet
Andrew T. Selder:
Undecided
Iein Valdez:
Employease, Williamstown, MA, which provides benefits management over the Internet
Laurence H. Zill II:
Tripod, Williamstown, MA


<< >> Title Contents