COMPUTER SCIENCE DEPARTMENT

This has been an exciting year for the Computer Science Department. While we missed the daily presence of Prof. Bill Lenhart, who just completed his first year as the College’s Provost, we were very happy to welcome two new faculty – Brent Heeringa and Morgan McGuire. Prof. Heeringa joined our department after completing his Ph.D. at the University of Massachusetts at Amherst. His research specialty is approximation algorithms. Prof. McGuire, who received his Ph.D. from Brown University, does work in the areas of graphics and computer vision. His research touches on a wide range of applications, including computer games. The department is excited to welcome another new faculty member, Jeannie Albrecht, who will join us as of July 1. Prof. Albrecht’s research area is distributed systems. She completed her Ph.D. at the University of California, San Diego.

While saying farewell to this year’s graduates, we welcome 18 members of the class of 2009 as new majors. They join 13 majors from the class of 2008.

Every year many of our students get involved in interesting research projects. This year, three members of the class of 2007 – Alexandra Constantin, Michael Gnozzio, and Paul Stansifer – completed honors theses. In addition, Bartley Tablante '07 did an independent study project with Prof. McGuire. Inspired by the user interfaces depicted in the science fiction film Minority Report, Bartley created an algorithm to track a human operator in a video stream and use that captured motion to interact with a 3-D world. Other students working with faculty on research included Kristof Redei ‘07, with Prof. Danyluk, M. Catalin Iordan '08, with Prof. Heeringa, and Kyle Whitson and Sean Barker (both ‘09), with Prof. McGuire. Their work, and that of others, is described below. Work is just beginning for this year’s summer research assistants.

Each week, colloquium speakers visit the department and discuss research with interested students and faculty. Through the generosity of the Class of 1960, the department augments its colloquium series with special programs of talks and related events that allow students even greater opportunity to interact with important contributors to computer science. This year Terrence Masson, founder of Digital Fauxtography, a company that specializes in visual special effects for film and video games, spoke on the state of computer graphic production in short film and feature length animation. As part of the Class of 1960 Scholars Program, several students were invited to special events with the speaker. This year’s scholars were:

Several additions to our curriculum were made this year, primarily in the areas of graphics and games. Prof. McGuire developed a new Winter Study course, Game Design Studio, in which students explored the art and theory of professional game development. Prof. McGuire also redesigned the Computer Graphics elective, CSCI 371.

Prof. Duane Bailey released Mead, his scheme-based modeling system. Students of The Art & Science of Computer Graphics used Mead to develop a wide range of models for rendering both realistic and abstract images and animations. Readers are encouraged to visit his website to check out the software. On the campus network, class images can be viewed at http://cswiki.cs.williams.edu/wiki/index.php/Computer_Science_109.

Bailey also worked with Kathryn Lindsey this spring on research that investigated the development of rules for Conway’s Game of Life when played on Penrose tilings. This new approach involves modeling these aperiodic tilings as two-dimensional projections of periodic lattices in 5-space. Their hope is to show that robust gliding patterns can be defined for Penrose tiles, the first step toward understanding population dynamics in more amorphously structured naturally occurring networks.

Photo: Great Horned Sphere - generated by Kathryn Lindsey ‘07, using Mead

Tutorial students from Modern Computer Architecture worked with Bailey to develop an experimental 4-core RISC processor chip that is less than 2mm on a side.

Bailey is a reader on the Goldwater science scholarship panel. He participates in review panels for various NSF programs, and reviews work for journals and conferences in computer science and mathematics.

Prof. Andrea Danyluk worked with two honors students this year, Michael Gnozzio ‘07 and Alexandra Constantin ‘07. Both completed theses on topics in machine learning. Michael developed two new algorithms: TNCA (the Triple Node Cascade Algorithm) and CAFIE (the Cascade Algorithm For Input Elimination), which automatically construct neural networks for classification tasks based on input data. Neural networks are a well-established mechanism for performing classification tasks and can be “taught” to correctly classify inputs based upon a set of “training examples.” A difficulty, however, is that the architecture of a neural network is generally handcrafted. Michael’s work extends research that aims to eliminate the need for handcrafting neural network architectures. Alexandra’s research addressed brain-computer interfaces (BCIs). Specifically, she developed algorithms for detecting subject-dependent EEG patterns for specific motor imagery tasks, such as imagined left hand movement and imagined right hand movement. The identification of such patterns in EEG signals can be used to automatically control a device (such as a computer mouse) for patients who are physically unable to do so.

Danyluk also continued to work on the development of algorithms for automatic identification of individual spotted salamanders from digital photographs. This project is collaboration with Prof. Hank Art of the Biology Department. Kristof Redei ‘07 worked with Prof. Danyluk on this project, continuing the work done by Myron Minn-Thu-Aye ‘07 last summer. This summer, David Moore '10 will join the project.

Danyluk served as the Tutorials Chair for AAAI-2007 (the National Conference on Artificial Intelligence) and the Panels and Special Sessions Chair for SIGCSE 2007 (the annual Symposium on Computer Science Education). She also taught a 6-week course Artificial Intelligence: Image and Reality for the Berkshire Institute for Lifetime Learning.

Prof. Stephen Freund continues to study how to verify properties of programs with lightweight analysis tools. Sigma Xi invited him to present two lectures on this work at Williams last October. The lectures were entitled “Squashing the Bugs: Tools for Building Better Software” and “Atomizer: A Dynamic Bug Finder for Large Systems.” In the talks, he discussed why it is so hard to create reliable software; various program checking techniques to find bugs; and a program checker that he designed to detect atomicity violations (one particularly pernicious type of error in concurrent programs).

Freund also received a National Science Foundation CAREER Award of $400,000 for his work on “Hybrid Atomicity Checking.” A routine is atomic if its execution is not affected by and does not interfere with concurrently executing threads. Both static and dynamic checkers have been designed to enforce atomicity specifications, but both approaches have inherent limitations that impact precision, coverage, and usability. Freund will synthesize the best aspects of such static and dynamic atomicity checking techniques to create hybrid checkers for validating precise, behavioral atomicity specifications. Such checkers enable more precise specification of a program’s atomicity requirements, offer better usability and scalability than existing tools, and support a modular and less error-prone concurrent programming methodology. CAREER awards are often considered the most prestigious awards granted by the NSF, and they are specifically designed to support “teacher-scholars who most effectively integrate research and education within the context of the mission of their organization.”

Freund published a number of papers during this past year in collaboration with Cormac Flanagan (UC Santa Cruz), and with his colleagues.

This past year, Freund also served as the advisor for Paul Stansifer’s honors thesis, “Alias Annotations to Improve Garbage Collection.” Alias annotations capture sharing relationships in pointer-based data structures, such as which objects have unique referring pointers. Specifying these structural properties has obvious software engineering benefits, and modular checkers can verify such annotations. However, garbage collectors can also exploit this information to improve performance. For example, if a unique reference to an object is set to null, that object can be freed immediately, without waiting for a collection to occur. Paul demonstrated that on a variety of small benchmarks, alias annotations enabled a standard Mark-and-Sweep collector to perform many fewer collections and reduced run times by as much as 10% to 15%.

Prof. Brent Heeringa, who returned to the Computer Science Department this past fall after visiting Williams as an instructor during 2003-04, tried several new pedagogical approaches when teaching the upper level Theory of Computation and Algorithm Design courses, including the Socratic method when investigating advanced topics.

Heeringa continued his work on approximation algorithms and lower bounds on approximation. Approximation algorithms provide provably near-optimal solutions to computationally intractable optimization problems. As a result, they are a popular and effective means of coping with difficult real-world phenomena like scheduling classrooms under myriad constraints, finding optimal snow plow routes in large cities, or developing effective strategies for a simple game of 20 questions. Finding near-optimal solutions to the latter question continues to be the primary study of Heeringa’s research. This problem is known as Decision Tree (DT) and it plays a significant role in areas as diverse as medical diagnosis and survey design. This summer, Heeringa is working with Son Ho ‘08 on finding stronger lower bounds to the DT problem. In March, Heeringa gave an invited talk on this work at the University of Massachusetts, Amherst.

Heeringa also initiated work on several new problems. Collaborating with M. Catalin Iordan ‘09, Heeringa investigated approximation algorithms for finding the minimum reset sequence in self-synchronizing automata. Self-synchronizing automata naturally model many workflow tasks in factory-like settings. Heeringa is continuing the work this summer with Austin Stanley ‘10. In particular, they are developing new algorithms to find counter-examples to a 40-year-old open conjecture in self-synchronizing automata.

Heeringa continues to consult for the search engine marketing firm Adverplex Inc. He helped Prof. Micah Adler (University of Massachusetts, Amherst) launch the company in 2005.

Heeringa attended the 2006 Foundations of Computer Science Conference, the 2007 Symposium on Discrete Algorithms, and the 2007 Symposium on Theory of Computing (STOC) where he organized the first-annual Association for Computing Machinery STOC Student Research Competition (SRC). This is an international effort to encourage undergraduate research in theoretical computer science. Heeringa chaired the paper selection committee, judged the final poster and oral presentations, and handled publicity for the event. Heeringa also received a travel grant from the Special Interest Group on Algorithms and Computation Theory (SIGACT) in recognition of his work on the STOC SRC. Heeringa reviewed papers for the 2007 Consortium on Computing Sciences in Colleges conference.

Photo: Eric Muller '09 presents a design review of his final project to the Computer Graphics class.

Prof. Morgan McGuire chaired the Animation Session at the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games in Seattle, WA this May and acted as publicity chair for the conference.  On campus, he hosted a monthly colloquium series explaining the computer science behind films and games and exploring how that technology impacts society. 

This year, the Computer Science Department added a new graphics lab to support work on computer graphics and vision. New results from the lab include processing video 100x faster than conventional methods (with Kyle Whitson ‘09), leveraging computers to conserve – instead of consume! – energy (with Kathleen Creel ‘10), and combining captured human animation with real-time physics (with Bartley Tablante ‘07, as described above).

Next year, Prof. McGuire’s Game Design Studio Winter Study course will be expanded into the introductory computer science and studio art course, Strategy and Interaction CSCI 107.  This class will teach computer science, economics, and art through analysis and synthesis of board and video games.

Over the last few years, Prof. Tom Murtagh has pioneered a new approach to teaching introductory computer science courses. He has worked to design an alternative to traditional introductory courses that focus narrowly on teaching programming skills. This year, with support from the NSF’s CCLI program, he has continued to develop materials for a new version of our introductory course that combines instruction in programming with an introduction to networking technology. This course uses the exploration of networking technology as a vehicle to motivate and focus the presentation of the techniques and principles underlying all work in computer science. Students in the course explore data representation techniques such as Huffman coding, apply basic techniques from probability theory to analyze Ethernet performance and the reliability of error detecting codes, study techniques for image compression, and learn quite a bit about Java programming in the process.

Prof. James Teresco continued his research on parallel and distributed computing, specifically in the area of dynamic load balancing for adaptive scientific computation in heterogeneous, hierarchical, and non-dedicated parallel computers. In particular, his interest is in supporting high-performance parallel computation in the types of computer systems that are found at smaller institutions such as Williams: networks of workstations and small clusters.

Modern parallel processing is being performed on everything from the largest tightly coupled supercomputers to clusters of workstations in the transient and dynamic environments found in Internet, or “Grid” computing environments. Hierarchical and heterogeneous systems are increasingly common and present new challenges for the development of efficient software, particularly influencing dynamic load balancing procedures. Teresco continued a collaboration with Dr. Karen Devine (Sandia National Laboratories) to develop support for architecture-aware load balancing in the Zoltan Toolkit (http://www.cs.sandia.gov/Zoltan/). Zoltan is a software library developed at Sandia that provides a common interface to a number of state-of-the-art partitioning and dynamic load balancing algorithms.

Teresco’s team is developing the Dynamic Resource Utilization Model (DRUM, http://www.cs.williams.edu/drum/) to address partitioning and dynamic load balancing on clusters with heterogeneous and hierarchical hardware resources. DRUM includes a model that encapsulates hardware resources and their interconnection topology, and provides monitoring facilities for dynamic evaluation of communication, memory, and processing capabilities. This work has been funded in part by Sandia National Laboratories. DRUM’s capability to support computation in heterogeneous environments was the focus of Teresco’s talk presented at Mount Holyoke College and Union College in February.

Recent efforts in the DRUM project focus on the efficient use of the “hyperthreaded” and multi-core processors that are now being used to construct computational clusters. This work was the focus of his talk at the SIAM Conference on Computational Science and Engineering in Costa Mesa, California.

Teresco is also investigating the efficient execution of parallel adaptive software in dynamic environments, in collaboration with Prof. Boleslaw Szymanski, Prof. Carlos Varela, and Prof. Joseph Flaherty (all of RPI), and Rensselaer Ph.D. candidates Kaoutar El Maghraoui and Travis Desell. As part of this project, the team is developing MPI/IOS, a middleware system that allows existing applications, written using the popular Message Passing Interface (MPI), to take advantage of transient and or unreliable computing resources with minimal modification. The work is described in a chapter entitled “Towards a Middleware Framework for Dynamically Reconfigurable Scientific Computing” in the volume Grid Computing: New Frontiers of High Performance Computing. Teresco served as a Ph.D. committee member for El Maghraoui, who completed her thesis in April.

Teresco and his former thesis student, Travis Vachon ‘06, traveled to Innsbruck, Austria, to present the paper “Automated Dynamic Redistribution of Virtual Operating Systems under the Xen Virtual Machine Monitor,” at the IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN 2007) in February.

Teresco, Prof. Ali Erkan (Ithaca College), and Prof. James Heliotis (R.I.T.) served as co-chairs for papers at the Twelfth Annual Consortium for Computing Sciences in Colleges Northeastern Conference (CCSCNE 2007), held at R.I.T. in April. See http://www.ccscne.org/2007/.

On the teaching side, Teresco led an enthusiastic group of students in the Winter Study class LEGO Robot Engineering. Students spent the first few weeks of the month building and programming robots in an increasingly complex series of exercises. Then, each group proposed a design for a robot to carry out a task of their choosing. Robots were designed to play “tag,” to fire projectiles (marbles), and to sense a gap in the surface and deploy a bridge to continue across. The term culminated in a robotics exposition where the final robots were demonstrated to classmates, friends, faculty, and a group of local middle school students.

Teresco is leaving Williams at the end of the 2006-07 academic year. He will be joining the faculty at Mount Holyoke College in South Hadley, MA.

Terrence Masson, Digital Fauxtography and VFX, Class of 1960 Scholars Speaker

“CG101: A Computer Graphics Industry Reference”
“SIGGRAPH Film Festival Screenings”
Prof. Tom Ellman, Vassar College

“Synthesis of Hybrid Automata from Temporal Logic Specifications with Applications in Computer Animation”
Prof. Emery Berger, University of Massachusetts at Amherst

“Automatically Tolerating and Correcting Memory Errors”
Rob Gallerani and Jan-Erik Steel, Vicarious Visions

“A Brief Look into Video-Game Development”
Computer Science Faculty, Williams College

“Life after Williams: Graduate School Opportunities”
Prof. Srinivas Akella, Rensselaer Polytechnic Institute

“Coordinating Multiple Moving Objects: From Robots to Microdroplets”
Al Reed, Founder, Demiurge Studio

“Individualized Educational Systems”
Robert A. Hearn, Ph.D., Dartmouth College

“Games, Puzzles, and Computation”
Prof. Tim Huang, Middlebury College

“Beyond Deep Blue: Advances in Computer Go”
Charles Sutton, University of Massachusetts at Amherst

“Natural Language Processing and the Scientific Literature”
Prof. Craig S. Kaplan, University of Waterloo

“Complexity and Aesthetics in Computer-Generated Mazes”
Computer Science Faculty, Williams College

“Ongoing Research in Computer Science”
Max Ross, Google

“Where Were You on the Night of June 3^rd? Preserving Standard Hibernate
Programming Paradigms with a Bitemporal Schema”
Prof. Drew Endy, Massachusetts Institute of Technology

“Structure and Uncertainty in Robotic Motion Planning”
Prof. Morgan McGuire, Williams College

“New Library Challenges from Games Research”
“Visual Culture: Non-Photorealistic Rendering”
“Real-Time Cartoon Rendering of Smoke and Clouds”
“Music Video Games”
“Odd Couples: 3D Film Screenings”
“Art and Science of Board Games”
“Holiday Gaming Guide”

Students discussed their summer research or work experiences

“What I Did This Summer: Part I”
“What I Did This Summer: Part II”
Paul Stansifer '07

“Using Alias Annotations to Improve Garbage Collection”
Michael Gnozzio '07

“The Cascade Algorithm for Input Elimination”
Alexandra Constantin '07

“A Brain-Computer Interface for the Classification of Motor Imagery”

Andrea Danyluk

“Tutorials in the Sciences: Tradeoffs”
Conference on Tutorial Education, Lawrence University
Brent Heeringa

“A Log-Factor Approximation for Decision Trees”
Theory Seminar, University of Massachusetts at Amherst
Morgan McGuire

“Single-Pass Shadow Volumes for Arbitrary Meshes”
ACM SIGGRAPH Posters Session, San Diego, CA

“Open Source Toolchains”
ACM SIGGRAPH Symposium on Video Games Panel Discussion, San Diego, CA

“Innovative Computer Input Devices”
Bennington College

“Non-Photorealistic Rendering of Smoke and Clouds”
Union College

“Real-Time Cartoon Rendering of Smoke and Clouds”
ACM Symposium on Non-photorealistic Animation and Rendering, Annecy, France

“Real-Time Triangulation Matting Using Passive Polarization”
ACM SIGGRAPH Sketch, Boston, MA

“World Space Torques for Character Animation under Simulation”
ACM SIGGRAPH Sketch, Boston, MA

“Mechanism Design for Fun and Profit”
Stanford University

“Efficient Content Creation”
Vicarious Visions, Albany, NY
Thomas P. Murtagh

“Breadth with Depth in a CS1 Course”
Dennison University CS1 Workshop for Computer Science Faculty, Granville, Ohio
James Teresco

“Resource-Aware Parallel Computation for Modern Clusters”
Union College, Mount Holyoke College

“Automated Dynamic Redistribution of Virtual Operating Systems under the Xen Virtual Machine Monitor”
IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN 2007)

“Dynamic Load Balancing for Hyperthreaded and Multi-Core Cluster Nodes”
SIAM Conference on Computational Science & Engineering

“Chip Multiprocessors: Parallel Computation for the Desktop”
Mount Holyoke College