Several members of our department’s faculty have moved in and out of administrative positions over the course of this year. At the beginning of the year, Andrea Danyluk concluded a year of service as the Acting Dean of Faculty for the college. She was excited to return to the classroom, teaching a diverse set of courses ranging from our introductory course to a tutorial on Machine Learning (her research area) to the senior seminar in Cognitive Science. At the end of the year, Prof. Bill Lenhart completed six years of service as Provost of the College, where he helped guide the College through the financial difficulties of the last few years. Bill begins a well-deserved sabbatical leave this fall. The department looks forward to his return to teaching. Finally, Prof. Tom Murtagh completes his term as Chair of the Computer Science Department at the end of this year. Prof. Steven Freud will assume this position. We appreciate the service all of these members of our department have provided.

(left to right) Diogenes Nunez ‘12, April Shen ‘12 and T. Andrew Lorenzen ‘12 viewing a research poster at the end of the Summer Science Research Session in August 2010.

Each year the department participates in a special lectureship program funded through the generosity of the Class of 1960. This fall, we welcomed Prof. Lance Fortnow from Northwestern University McCormick School of Engineering. His research spans computational complexity and its applications, most recently to micro-economic theory. His works on interactive proof systems and time-space lower bounds for satisfiability have led to his election as a 2007 ACM Fellow. In the spring, Prof. Luis von Ahn of Carnegie Mellon University visited our department. His research interests include encouraging people to do work for free, as well as catching and thwarting cheaters in online environments. He is most widely known for his contributions to the development of the captcha, those images of distorted letters you have to read and type to access certain web sites. He is the recipient of a MacArthur Fellowship. During their visits, each of these distinguished guests gave several talks and met with faculty and students. As part of the Class of 1960 scholars program, several students were invited to participate in special events. This year’s scholars were:

Class of 1960 Scholars in Computer Science

We were able to provide some of our students with another opportunity to interact with computer scientists outside our department in October when Kaylee Weyerhaeuser’11, Emily Yu’11, April Shen’13, and Lorraine Schmitt’13 attended the Grace Hopper Celebration of Women in Computing in Atlanta, Georgia along with Prof. Danyluk. This trip was made possible by funding we received from both the college and the Anita Borg Institute for Women in Technology. We are grateful for this support.

After spending the fall semester on maternity leave, Prof. Jeannie Albrecht spent the spring semester on sabbatical at the University of Massachusetts, Amherst. There she continued to develop Gush, which is a framework for configuring and controlling distributed applications (http://gush.cs.williams.edu). Gush is part of a National Science Foundation (NSF) funded project for creating GENI—a Global Environment for Network Innovations (http://www.geni.net). Kaylee Weyerhaueser (’11) and April Shen (’13) worked with Albrecht last summer on a graphical user interface for Gush, which originally began four years ago as an extension of Albrecht’s thesis work on Plush. A journal article on Plush was recently accepted for publication in the Association for Computing Machinery’s Transactions on Internet Technology (TOIT) journal, and will appear sometime in the next year.

Also as part of her work with GENI, Albrecht traveled to Washington, D.C. in November for the GENI Engineering Conference and demonstrated how Gush and GENI can be used to enhance undergraduate computer science curriculums. In addition, Albrecht began working on extensions to her previous work on distributed application management that focused on the challenges that arise in mobile applications. Specifically, this new project aims to make applications that run in volatile mobile networks more reliable. Danny Y. Huang (’11) worked with Albrecht on this task for his senior thesis this year. Danny will join University of California at San Diego in pursuit of a Ph.D. this fall.

Albrecht recently had a paper accepted at Simplex, a workshop that focuses on Simplifying Complex Networks for Practitioners. The paper describes a new algorithm for automatically detecting “knees” in performance curves. Knees typically represent the point of diminishing returns, and many systems have developed ad hoc methods for finding these knees. Albrecht’s work aims to provide a general-purpose method for detecting knees in a way that is not application-specific. Albrecht will travel to Minneapolis in June and present her results. This project is joint work with Barath Raghavan of ICSI, David Irwin of University of Massachusetts, Amherst, and Ville Satopää (’11). Ville will attend the University of Pennsylvania in pursuit of a Ph.D. in Statistics this fall.

Aside from distributed and mobile application management, Albrecht also began working on a new green computing project at the University of Massachusetts, Amherst this spring. The project aims to lower the peak energy usage of homes by scheduling “background” appliances (e.g., refrigerators, dehumidifiers, etc.) in a way to avoid high peaks in energy usage. Albrecht recently submitted a paper to the International Conference on Ubiquitous Computing documenting her results. As a next step, Albrecht and her colleagues plan to experiment with the use of renewable energy sources and batteries to further reduce the strain put on the electric grid. The project is joint work with Prof. Prashant Shenoy, David Irwin, and Sean Barker (’09) at the University of Massachusetts, Amherst.

Prof. Duane Bailey worked with two seniors this year on independent research. Steve Rubin’11 completed honors work with Bailey, developing a new approach to visualizing the very large communication structures that are often associated with highly parallel programs. The approach makes use of the information that programmers often provide when they increase the number of processors used by a parallel program. Jack Wadden’11 worked with Bailey on a design for a time-sliced field programmable gate array (FPGA) that might be used in conjunction with traditional processors. The approach would allow programmers to bundle alternative hardware implementations of computationally intensive algorithms with software.

Bailey begins a new project with Jennifer Gossels’13 this summer, modifying a technique called “literate programming,” that will support the process of writing about programs. The immediate goal of the system will be the development of a new text on data structure design for Python.

Bailey continues to work with Pittsfield High physics teacher Brad Whateley, who teaches Principles of Engineering. Whateley and Bailey co-designed a number of hardware experiments that demonstrate the use of logic in computer engineering.

Bailey continued as a member of the NSF advisory panel on the redesign of the Advanced Placement exam in Computer Science. The curriculum is part of a national effort to boost participation in Computer Science. Bailey continued as a member of the national panel of readers for the Goldwater, a congressional scholarship that recognizes the nation’s best undergraduate students. He is also a reviewer for the National Science Foundation.

Prof. Andrea Danyluk returned to the department after a year of administrative work. She was excited to teach a diverse set of courses ranging from our introductory course to a tutorial on Machine Learning (her research area) to the senior seminar in Cognitive Science.

Danyluk supervised two honors theses this year, one in Computer Science and the other in Cognitive Science. In Computer Science she worked with Nick Arnosti’11. Nick’s work addressed two related issues: fast training of linear Support Vector Machines (SVMs) and feature selection. Research has demonstrated that SVMs for classification purposes can be learned and applied effectively across a wide set of domains. Nick was able to significantly improve upon techniques for fast training of linear SVMs, and demonstrated that his techniques worked best on data sets with a high example-to-feature ratio. Nick then developed a new method for feature selection based on the work of Shen et al. as well as a theoretical framework for the analysis of his method and Shen’s. This framework relates Shen’s method to the Bayes-optimal classifier and makes predictions about situations in which his method or Shen’s would be best to use.

In Cognitive Science, Danyluk co-advised the thesis of Patricia Klein’11 together with Prof. Nate Kornell in the Psychology Department. Patricia’s work focused on the testing effect, which refers to the phenomenon that active retrieval of information tends to lead to greater learning than re-presentation. Together Patricia and Prof. Danyluk developed a computational model to explore two possible causes of the testing effect: mediation and inhibition.

Danyluk continued her work as a board member of the CRA-W, the Computing Research Association’s Committee on the Status of Women in Computing Research, where her primary role is to administer an undergraduate research grant program. This year she also developed an extensive set of resources on undergraduate research mentoring and ran a workshop on the same topic. She has also begun work as a member of the steering committee for the ACM/IEEE Computer Science Curriculum 2013, whose goal is to develop international curriculum guidelines for undergraduate programs in computer science. She continues her work with the Liberal Arts Computer Science Consortium.

Prof. Stephen Freund has continued his work on tools to help programmers more easily find defects in software. As part of this work, he published the paper “FastTrack: Efficient and Precise Happens Before Race Detection” in Communications of the ACM. The paper describes a new technique for finding race conditions, a particularly pernicious type of bug caused when multiple parts of a program try to access a shared resource (such as a file or printer) at the same time.

In addition, he presented his work at several venues, including Harvard University and Cornell University. He also presented an overview of his research at Williams in a talk entitled “Stopping the Software Bug Epidemic,” which was part of the Williams College Faculty Lecture Series this spring.

Last summer, Freund work with Diogenes Nunez’12 on a summer science research project entitled “ÄúStatistical Sampling for Dynamic Concurrency Analyses.” The goal of this work was to reduce the overhead of monitoring programs for defects caused by checking every operation performed by the processor. Instead, we examined the effectiveness of statistically sampling the operations in a way that still enables the monitor programs with a lower run-time overhead while still catching defects with a fairly high probability.

Freund served on the program committee for several workshops and conferences this past year, including the ACM Conference on Principles of Programming Languages. He is also currently serving on the Programming Languages Education Board, the national committee in his research community that focuses on issues surrounding undergraduate education.

Prof. Brent Heeringa completed his fifth year as Assistant Professor in the Computer Science Department at Williams College. Heeringa taught Theory of Computation in the fall and Algorithm Design and Analysis in the spring.

Heeringa advised one senior honors thesis.  Erdem Sahin’11 developed, adapted and analyzed a suite of minimum spanning tree algorithms for the increasingly relevant MapReduce paradigm of computation.

Based on work from his sabbatical at BU, Heeringa, in collaboration with John Byers (BU), Giorgos Zervas (BU) and Michael Mitzenmacher (Harvard University), published Heapable Sequences and Subsequences at the 2011 Workshop on Analytic Algorithmics and Combinatorics. The work is motivated by the classic secretary problem where a committee sequentially interviews candidates for a secretarial position. When interviewing a candidate, the committee learns the candidate’s rank relative to all the previously interviewed candidates. Immediately following the interview, the committee can either offer the job to the candidate (which he will always accept) or pass on the candidate, in which case the committee considers the next person. Perhaps surprisingly, the optimal hiring strategy samples the first 37% of the candidates and then offers the job to the first candidate in the remaining 63% that exceeds the best candidate seen so far. Heeringa and his colleagues extended these problems to scenarios where the committee is interested in hiring an organization with the constraint that a candidate will only work under someone who is ranked higher.

Heeringa also continued his research on data structures and approximation algorithms. Working with Gordon Wilfong (Bell Labs) and Glencora Borradaile (Oregon State University), Heeringa published the 1-Neighbour Knapsack Problem at the 2011 International Workshop on Combinatorial Algorithms. Building on M. Catalin Iordan’s ’09 (Stanford University) honors thesis, Heeringa together with Iordan and Louis Theran (Temple University) developed the Line-Leaf Tree––a new data structure for maintaining a dynamic partial order. The research will appear at the 2011 Algorithms and Data Structures Symposium. This work includes experiments based on T. Andrew Lorenzen’s’12 implementation of the Line-Leaf Tree.

A $200,000 National Science Foundation award supports all of Heeringa’s research.

This past year Heeringa was selected as the University of Minnesota, Morris (UMM) 2010-11 Latterell Visiting Alumnus which provides “a unique opportunity to expose UMM students to the enormous breadth of career options that exist for well prepared and articulate graduates of Morris’s science and mathematics programs.” Heeringa traveled to Minnesota in November to give a series of public lectures and talks.

Heeringa reviewed papers for Information Processing Letters, Discrete Applied Mathematics, and the 2011 Symposium on Discrete Algorithms. He attended the 2010 Foundations of Computer Science (FOCS) conference held in Las Vegas, NV, the 2011 Symposium on Discrete Algorithms (SODA) and 2011 Workshop on Analytic Algorithmics and Combinatorics held in San Francisco, the 2011 Conference on Implementation and Application of Automata held in Winnipeg, and 2011 International Workshop on Combinatorial Algorithms held in Victoria, BC. Heeringa also traveled to Swarthmore College this past spring as an external honors examiner.

Prof. Morgan McGuire collaborated with NVIDIA Research and the Vicarious Visions game studio on massively-parallel Monte Carlo methods for computer graphics throughout the year. Their work directly affects consumer products such as film and video games today and has significant implications for how financial, medical and scientific modeling will be done in the future.

From the shading on the leaves of the jungle in the film Avatar to tracking the interactions of individual drug molecules in a pharmaceutical study, there are many problems for which computing a result every element of truly massive data is impossible. This isn’t just a limitation of today’s computers—even on the fastest computers that we might ever build we could not solve many of these problems by brute force. The only approach is to carefully sample millions of individual data in a representative way and then estimate the net impact of trillions elements. This process is called stochastic sampling and reconstruction, and it is how most scientific simulation is performed today. Prof. McGuire invented several new methods at Williams for increasing the quality of the result while reducing the number of samples. This year that work led to several new solutions for classic problems in computer graphics: shadowing from nearby objects, proper rendering of translucent surfaces, and aliasing that appears as jagged edges on lines in computer images.

Looking forward, he is currently collaborating on separate projects with Kefei Lei’10 (at Brown University) and Marc Blackstein ’99 (NVIDIA), as well as advancing stochastic methods in the graphics lab on campus. He is particularly excited to join the leading researchers on the antialiasing problem across industry and academia to teach a course for researchers at this year’s SIGGRAPH conference in Vancouver, CA.

Prof. McGuire travelled to present work at several conferences and gratefully accepted first and second place research awards in the High-Performance Graphics conference with his coauthors for their two papers in that venue last summer.

He edited the Special Section on the Symposium on Interactive 3D Graphics and Games in the IEEE Transactions on Visualization and Computer Graphics journal, the Journal of Graphics, Game, and GPU Tools, and the Proceedings of the ACM SIGGRAPH Symposium on Non-Photorealistic Animation and Rendering.

Prof. Tom Murtagh continued his work investigating congestion control mechanisms for Internet protocols. During the summer of 2010, Murtagh worked with Michael Dinku’11 on the analysis of traces of Internet traffic. The goal of this work is to identify techniques that might be used within an Internet router to efficiently distinguish different types of data flows in order to design routers that more effectively allocate available bandwidth.

Murtagh also began a new project on improved contention resolution in broadcast networks like Ethernets and WiFi networks. He worked with Katherine Stevenson’12 on the construction of a simulator to support experimental evaluation of contention resolution schemes. In addition to its research goals, this project provided the framework for a new, simulation-based project in the tutorial course on computer networks that Murtagh offered in the fall.

Murtagh attended the USENIX Networked Systems Design and Implementation conference in June 2010.

Department Colloquia

Prof. Morgan McGuire, Williams College

“Ambient Occlusion Volumes”

Prof. Duane Bailey, Williams College

“In Search of the Programmable Tatoo”

Computer Science Faculty

“Everything you need to know about graduate schools and more”

Giogos Zervas, Ph.D. Candidate, Boston University

“Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank”

Prof. Andrew McGregor, University of Massachusetts, Amherst

“Data Streams, Dyck Languages, and Detecting Dubious Data Structures”

David Luebke, Ph.D., Director of Research, NVidia Research

“Democratizing Supercomputing: the surprising story of GPU computing”

Prof. Hannah Wallach, University of Massachusetts, Amherst

“P versus NP: An Epic Struggle”

Hanspeter Pfister, Gordon McKay Prof. of the Practice, Harvard University

“High-Throughput Science”

Prof. Audrey Lee St. John, Mount Holyoke College

“Rigidity Theory: from Foundations to Applications”

A.J. Brush ’96, Researcher, Microsoft

“Everyday Technology for Families”

Robin Stewart ’06, The Omni Group

“Direct Manipulation 2.0: Why scientific software should also be fun for 3-year-olds”

Prof. Kevin Fu, University of Massachusetts, Amherst

“Trustworthy Medical Device Software”

Prof. Richard Wicentowski, Swarthmore College

“Computational Semantics and Lexical Substitution”

Prof. Stephen Freund, Williams College

“FastTrack: Efficient and Precise Dynamic Race Detection”

Computer Science Faculty

“Graduate School – How to Apply and What to Expect”

Prof. Douglas Turnbull, Swarthmore College

“Combining Audio Content and Social Context to Improve Music Discovery”

Computer Science Alumni Panel

“Beyond Williams – Life After Williams”

Prof. Kristina Striegnitz, Union College

“Evaluating Natural Language Generation Systems in Online Virtual Environments”

Department Student Colloquia

Off-Campus Colloquia

Jeannie Albrecht

“GENI in the Classroom,” GENI Engineering Conference 9, November 2010
“Finding a ‘Kneedle’ in a Haystack: Detecting Knee Points in System Behavior,” Simplex Workshop, June 2011

Andrea Danyluk

“Identification of Individual Spotted Salamanders”

Willamette University, Salem, OR

Union College, Schenectady, NY

“How do I start my own research program?”

Grace Hopper Celebration of Women in Computing, Atlanta, GA

“Making the Most of Undergraduate Research”

“Time Management”

SIGCSE 2011, The 42nd ACM Technical Symposium on Computer Science Education, Dallas, TX

“Balancing Graduate School and Personal Life”

“Academic Career Paths: Research and Teaching”

CRA-W Graduate Cohort Workshop, Boston, MA

Stephen Freund

“FastTrack and Jumble: Efficient and Precise Dynamic Detection of Destructive Races”

Harvard University, November 2010

“FastTrack and Jumble: Efficient and Precise Dynamic Detection of Destructive Races”

Cornell University, March 2011

Brent Heeringa

“Searching in Dynamic Partial Orders”

Invited talk at the University of Minnesota, Morris

“From Startups to Scholarship: Life in the Liberal Arts after UMM”

Invited talk at the University of Minnesota, Morris

“Minimum Reset Sequences”

Conference on Implementation and Application of Automata

“Heapable Sequences and Subsequences”

Workshop on Analytic Algorithmics and Combinatorics

Morgan McGuire

“The Big Picture: The Science of Computation for Visual Communication”

Harvard University, Cambridge, MA, December 1, 2010

“A New Analytic Solution for the Ambient Occlusion Problem”

University of Toronto, Toronto, Ontario, Canada, July 15, 2010

University of Iowa, Iowa City, IA, November 19, 2010

“Real-Time Stochastic Rasterization”

University of Waterloo, Waterloo, Ontario, Canada, July 13, 2010

Postgraduate Plans of Computer Science Majors