COMPUTER SCIENCE DEPARTMENT

The Computer Science Department enjoyed the presence of two visiting faculty members this year. Prof. Barath Raghavan joined the department as a Visiting Assistant Professor for the full academic year. Raghavan had recently received his Ph.D. from the Department of Computer Science at the University of California, San Diego. Prof. Alicia Wolfe joined us for the spring semester after completing her Ph.D. at the University of Massachusetts, Amherst. During the year Raghavan taught three courses – Data Structures, Theory of Computation, and Algorithms. Raghavan’s research interests fall primarily in the areas of networks and distributed systems. He collaborated on research projects throughout the year with Prof. Jeannie Albrecht and many of our students. He will continue in our department next year as a post-doctoral research associate. Wolfe taught an elective course, Artificial Intelligence. Wolfe’s research’s interests involve artificial intelligence and machine learning.

These temporary additions to our department were triggered by several temporary departures. Two of our newer faculty members, Prof. Brent Heeringa and Prof. Morgan McGuire were away on assistant professor leaves. Heeringa worked at Boston University for the year while McGuire worked at the NVDIA Research Laboratory. In addition, Prof. Andrea Danyluk moved from her office in our department to an office in Hopkins Hall where she served as acting Dean of Faculty while the college awaited the arrival of our new president, Adam Falk.

Each year the department participates in a special lectureship program funded through the generosity of the Class of 1960. This fall, we welcomed Dr. Melanie Mitchell from Portland State University and Santa Fe Institute. In her work, Prof. Mitchell applies techniques from artificial intelligence and machine learning to the understanding of complex systems. Her most recent book, “Complexity: A Guided Tour”, was named by Amazon.com as one of the ten best science books of 2009. In the spring, Prof. Paul Hudak of Yale University visited our department. Prof. Hudak has made many contributions to the field of programming languages, including playing a major role in the development of the language Haskell. 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:

Prof. Jeannie Albrecht continued to investigate the challenges of distributed application management as part of GENI <http://www.geni.net>, a National Science Foundation (NSF) funded project for creating a Global Environment for Network Innovations. In particular, Albrecht has continued to work on the development of a system called Gush, which is a framework for configuring and controlling distributed applications <http://gush.cs.williams.edu>. In addition to her work with GENI, last fall Albrecht received a CAREER award for $400,000. The CAREER award is the most prestigious award NSF gives to junior faculty. This grant will fund her extended work on distributed application management in mobile environments for the next five years.

In the context of application management, Albrecht’s current research focuses on two specific problems. First, she is exploring how to extend Gush to support volatile environments with frequent disruptions in network connectivity, such as wireless sensor networks or networks comprised of mobile devices. Danny Y. Huang ’11 worked with Albrecht on this task for the past three semesters, and will continue next year as part of his senior thesis. The second aspect of Albrecht’s research involves the development of a graphical user interface for Gush called Nebula <http://plush.cs.williams.edu/nebula/>. Kelsey Levine ’10 worked on application visualization using Nebula last summer, and Kaylee Weyerhaueser ’11 and April Shen ’13 will continue the project this summer.

Antal Spector-Zabusky ’12 explains his research project
during the summer research program's poster session.

In addition to Gush, last year Albrecht explored a new project with Prof. Barath Raghavan, Antal Spector-Zabusky ’12, and Ville Satopaa ’11. The project investigated how distributed resources can be shared to increase the utility of the resources for all users. The work ultimately resulted in two separate conference paper submissions. Antal Spector-Zabusky also won a prestigious Goldwater Scholarship.

In preparation for her upcoming sabbatical at the University of Massachusetts, Amherst, Albrecht continued to collaborate with Prof. Brian Levine and Prof. Mark Corner (both at the University of Massachusetts, Amherst) to address the challenges associated with running experiments on mobile/sensor networks. Albrecht plans to leverage the infrastructure created by Levine and Corner to experiment with partially predictable resource scheduling in mobile environments during the upcoming year.

During Winter Study, Albrecht and Prof. Murtagh jointly supervised six students — Kelsey Levine ’10, Moaj Musthag ’10, Dan Kenefick ’11, Emily Yu ’11, Josephat Koima ’12, and Diogenes Nunez ’12— who independently explored iPhone development. The students developed an application that allows members of the campus community to easily obtain dining hall menus from their iPhones. We are planning to release this application to the public very soon.

In the classroom, Albrecht taught an updated version of Distributed Systems (CSCI 339), in addition to Data Structures (CSCI 136) and Introduction to Computer Science (CSCI 134). The highlight of CSCI 339 was the use of Amazon’s Elastic Compute Cloud <http://aws.amazon.com/ec2/>. Through a generous grant from Amazon, the students in the course were able to experiment with the widely used Hadoop/MapReduce framework for efficiently processing massive amounts of data in parallel on pre-configured clusters of machines provided by Amazon.

Albrecht presented a paper this year at the Sixth International Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities (TridentCom) in Berlin, Germany. She gave two invited talks at the IEEE Conference on Peer-to-Peer Systems (P2P) in Seattle, WA. She also gave talks at the GENI Engineering Conferences in Durham, NC and Seattle, WA, the Diversity Workshop of the ACM Symposium on Operating System Principles (SOSP), and the NSF workshop on Archiving Experiments at the University of Utah. In October, Albrecht attended the Grace Hopper Celebration of Women in Computing in Tucson, AZ along with Prof. Andrea Danyluk and students Katie Creel ’10, Mayada Gonimah ’10, Kaylee Weyerhaeuser ’11, and Emily Yu ’11.

Prof. Duane Bailey collaborated with Jack Wadden ’11 to implement memory and I/O interfaces for their implementation of Prof. Murtagh’s WC34000 processor, a soft core implemented on a Xilinx Field Programmable Gate Array (FPGA). During the spring, Bailey’s tutorial on VLSI design designed new reconfigurable FPGA hardware.

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. The National Science Foundation has supported the initiative, which seeks to significantly broaden the scope of the course traditionally taught at the college and high school levels.

During the spring, Bailey participated in the NSF-sponsored initiative, National Lab Day, an effort that supports the development of curricula and lab resources by high school and college instructors. This year, Brad Whateley, a physics teacher in the Pittsfield High School taught a course, Principles of Engineering. Whateley and Bailey co-designed a number of hardware experiments that demonstrated the use of logic in computer engineering. After positive initial results, Whateley and Bailey are developing a low-cost circuit prototyping system for wider use in math and science courses at the high school level.

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. Bailey also participated in various review panels at the National Science Foundation, and reviewed papers for a number of professional publications.

Faculty and students attending the Grace Hopper Celebration of Women in Computing in Keystone, CO (Left to right - Mayada Gonimah ’10, Andrea Danyluk, Jeannie Albrecht, Katie Creel ’10, Kaylee Weyerhaeuser ’11, and Emily Yu '11

Prof. Andrea Danyluk spent the year in the Dean of Faculty Office, serving first as Acting Dean of the Faculty and then as Associate Dean. While in the Dean’s office, she remained connected to her computer science roots in a number of ways.

Danyluk, whose research is in the area of machine learning, a subfield of Artificial Intelligence (AI), supervised the honors thesis of David Moore ’10. David’s work addressed an issue related to Markov logic networks (MLNs). These are a recently developed formalism for compactly representing complex relationships and handling uncertainty in a principled manner. The deep transfer algorithm of Davis and Domingos proposes a method for automatically learning the structure of an MLN for a target domain of application by exploiting the structure of an existing MLN for some other domain. Dave explored several questions related to the deep transfer algorithm and to cross-domain transfer in general. He will present his results at the “Workshop on Statistical Relational Artificial Intelligence”, which will be held in conjunction with the National Conference on AI.

Danyluk is now beginning a new project in collaboration with Prof. Carla Brodley at Tufts University. The goal of this project from a practical standpoint is to develop a system that can automatically identify web pages that belong to computer scientists who are women or underrepresented minorities in order to develop a database for the outreach efforts of the CRA-W (the Computing Research Association’s board on the status of women in computing research) and the CDC (the Coalition to Diversify Computing). From a machine learning perspective, there are many interesting research questions to explore in this context. They will focus on issues related to active learning in which a machine learning system decides automatically what data would be most helpful for its own learning process. Three undergraduate students will be working on this project in summer 2010: Emily Yu ’11, Lucy Simko (from Washington and Lee University), and Heidy Khlaaf (from Florida State University). All will be resident at Tufts for the summer.

In spring 2010, Danyluk was named a CRA-W Distinguished Professor for the Cohort of Associate Professors Project for the second time. She continues her work with CRA-W as well as the Liberal Arts Computer Science Consortium.

Prof. Stephen Freund continued to work with his colleagues at UC Santa Cruz on tools to help programmers more easily find defects in software. As part of this work, he published two papers.  The first, “The RoadRunner Dynamic Analysis Framework for Multithreaded Programs” describes a system he designed with Cormac Flanagan (UC Santa Cruz). This is a general programming framework for trying out new bug finding techniques and comparing them to existing approaches.  The analysis framework is especially well-suited for implementing tools to find 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.

Freund also wrote a second paper, “Adversarial Memory for Detecting Destructive Races.” A bug in a program is often hard to find because it only causes a program to crash in rare situations that are hard to reproduce. This paper describes a tool that attempts to make any such intermittent bugs appear with much higher frequency so that developers can more easily identify and fix them. In addition, he presented his work at several venues, including the University of Massachusetts and University of California at Santa Cruz, as well as a conference on “Program Analysis for Software Tools and Engineering” in Toronto.  He was also the invited keynote speaker at Schloss Dagstuhl, a workshop on the “Design and Validation of Concurrent Systems” held in Germany.

Freund is currently serving on the Programming Languages Education Board, the national committee in his research community that focuses on issues surrounding undergraduate education.  He has written a number of papers on this topic, including one presented at a workshop on “Curricula in Concurrency and Parallelism,” held in Florida.

Prof. Brent Heeringa spent the year on AP leave at Boston University (BU) where he was Visiting Scholar. At BU, Heeringa collaborated with John Byers, Giorgos Zervas and Michael Mitzenmacher (Harvard University) on new combinatorial problems called heapable sequences. The work is motivated by the 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 interesting in hiring an organization with the constraint that a candidate will only work under someone who is ranked higher. This work is currently in submission for publication.

Heeringa also continued his research on data structures and approximation algorithms. Working with Gordon Wilfong (Bell Labs) and Glencora Borradaile (Oregon State University), Heeringa studied new approximation algorithms for a suite of constrained versions of the classic knapsack problem. This work is currently in submission for publication and available on the arXiv. 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 is currently in submission for publication. In addition, Heeringa advised T. Andrew Lorenzen ’12 on an implementation of the Line-Leaf Tree. Finally, with Michael Gerbush ’09 (University of Texas, Austin), Heeringa completed a line of research on approximating reset sequences in synchronizing automata. This work has applications in assembly line workflow and experiment design. A paper, co-authored with Gerbush, detailing the results of the research will appear at the 15^th Annual Conference on Implementation and Application of Automata in August. All of Heeringa’s research is supported by a $200,000 National Science Foundation award.

This past year Heeringa traveled extensively for research and pedagogical purposes. In the fall he gave invited talks at Bell Labs, Oregon State University, and the University of Minnesota, Twin Cities. He also used the trip to Minnesota to visit Prof. David Liben-Nowell at Carleton College in Northfield, MN. In October, Heeringa represented Williams College in Budapest as a member of a select committee of administrators and faculty that advised the fledgling Aquincum Institute of Technology (AIT). AIT will provide a study abroad opportunity for US undergraduates majoring in engineering and computer science starting spring of 2011.

Heeringa reviewed papers for SIAM Journal on Discrete Mathematics and SIAM Journal of Computing. He attended the 2009 Foundations of Computer Science (FOCS) conference held in Atlanta, GA and the 2010 Symposium on Discrete Algorithms (SODA) held in Austin, TX.

Prof. Morgan McGuire was also on AP leave during the 2009-10 academic year. Throughout the year, he worked with the NVIDIA Research laboratory. He explored new computational strategies for massively parallel Monte Carlo simulation motivated by specific problems arising in real-time 3D graphics. The results of this work appeared as a series of papers on techniques for approximating cinema-quality 3D in real time for games. They will impact the next generation of chip produced at NVIDIA, one of the leading parallel processor companies. McGuire is interested in parallel Monte Carlo strategies because they both directly affect consumer products today and have significant implications for how financial, medical and scientific modeling will be done in the future.

McGuire spent September 2009 at the Vicarious Visions subsidiary of Activision. There he learned about new problems in game development and consulted on lighting algorithms for the Marvel Ultimate Alliance 2 game for Xbox 360 and PS3. To archive the interesting new results he encountered in the literature and on the Internet while at these companies, McGuire started a blog that can be read at <http://graphics.cs.williams.edu>.

On campus, he served as a thesis advisor for Kefei Lei ’10. Lei’s independent research on surface scattering spans computer graphics and physics. It addresses a hole in scientific modeling of the large-scale interaction of matter and energy at the sub-micron scale just above molecules and just below features visible to the naked eye. Models of interaction at this scale are essential to computer graphics because they determine the appearance of a surface under specific lighting conditions. Lei’s work verified the validity of some long-standing computer graphics models in a limited context, while casting doubt on their accuracy in the general case. McGuire and Lei plan to continue collaborating when Lei enters graduate school at Brown University next semester.

McGuire attended several research conferences, including Interactive 3D Graphics and Games 2010 in D.C., High Performance Graphics 2009 and 2010 (which due to schedule shifts was held twice this academic year) in Los Angeles and Saarland, Germany, the joint symposium on Sketch-Based Interfaces and Modeling and Non-photorealistic Animation and Rendering (NPAR) 2010 in Annecy, France, and the 2010 SIGGRAPH annual conference in Los Angeles. He was the papers and general conference co-chair for NPAR and taught an invited course at SIGGRAPH. At I3D his early work on proximity shadows received the best poster award and at HPG his paper on real-time indirect light for games received second place in the best paper awards. With Eric Haines of Autodesk he edited a special issue of IEEE Transactions on Visualization and Computer Graphics and he served as an editor for the Journal of Graphics Tools.

Over the last few years, Prof. Thomas Murtagh has worked to design an alternative to traditional introductory computer science courses that focus narrowly on teaching programming skills. In particular, he has developed an introductory curriculum that uses the exploration of networking technology as a vehicle to motivate and focus the presentation of a broad overview of the techniques and principles underlying all work in computer science. This year, Murtagh gave a workshop on teaching such introductory courses at the annual SIGCSE Symposium on Computer Science Education. Murtagh also presented an overview of an innovative laboratory exercise developed for this new introductory curriculum as part of the Nifty Assignments panel at the SICCSE symposium.

During the summer of 2008, Murtagh worked with Michael Dinku ’11 on the analysis of traces of Internet traffic with the goal of identifying techniques that might be used within Internet router to efficiently distinguish between small and large data flows in order to design routers that more effectively allocate available bandwidth. This summer, Murtagh will continue this work with Michael. Murtagh attended the ACM SIGMETRICS conference in June 2010.

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”
Prof. Melanie Mitchell, Portland State University, Class of 1960 Scholars Lecture in Computer Science

“Complexity: A Guided Tour”
“Four Principles of Pattern Recognition in Living Systems”
Computer Science Faculty, Williams College

“Ongoing and Prospective Research in Computer Science”
Prof. Barath Raghavan, Visiting Professor of Computer Science, Williams College

“Computing in the Long Emergency”
Prof. Daniel Aalberts and Bill Jannen ’10, Williams College

“Introducing Zfold: Somewhere over the RNAbow”
Prof. Kathi Fisler, Worcester Polytechnic Institute

“How a Card Game Changed My View of Access-Control Policies”
Prof. Stephen Chong, Harvard University

“Inference of Usable Declassification Policies”
J. Nate Foster ’01, Postdoc, Princeton University

“Matching Lenses: Alignment and View Update”
Prof. Laura Toma, Bowdoin College

“Scalable Algorithms for Visibility Computation on Massive Terrains”
Dr. Paul Hudak, Yale University, Class of 1960 Scholars Lecture in Computer Science

“Euterpea: from Signals to Symphonies”
“Causal Commutative Arrows”
Andrea Danyluk, Williams College

“Identification of Individual Spotted Salamanders”

Dan Fast ’10, Erdem Sahin ’11, Mayada Gonimah ’10, T. Andrew Lorenzen ’12 and Katie Creel ’10

“What I Did This Summer”
David Moore ’10

"Rethinking Transfer Learning in Markov Logic Networks"
Kefei Lei ’10

“Assessment of the Microfacet Theory in Modeling Bidirectional Reflectance Distribution Functions”

Jeannie Albrecht

“Achieving Experiment Repeatability on PlanetLab”
University of Utah (NSF Archive Workshop), Salt Lake City, UT, May 2010

“Managing Distributed Applications using Gush”
TridentCom, Berlin, Germany, May 2010

“Running Experiments with Gush”
GENI Engineering Conference 7, Durham, NC, March 2010

“Academic Career Paths and Skills for Success”
SOSP Diversity Workshop, Big Sky, MT, October 2009

“Application Management and Visualization with Plush”
“PlanetLab – P2P Testing in the Wild”
P2P, September 2009, Seattle, WA

“PlanetLab Experimenter Tools”
GENI Engineering Conference 5, Seattle, WA, July 2009
Andrea Danyluk

“Promotion to Full Professor”

“Leadership in its Various Manifestations”
CRA-W Advanced Career Mentoring Workshop, Providence, RI

“The Best Way: Research by Undergraduates”
“Recruiting and Retaining at Primarily Undergraduate Institutions”
“The Graduate School Experience”
“Work/Life Balance and Time Management”
Grace Hopper Celebration of Women in Computing, Tucson, AZ
Stephen Freund

“Types for Concurrency”
Invited Keynote Lecture Schloss Dagstuhl, Germany, Aug. 2009

“FastTrack: Precise and Efficient Dynamic Race Detection”
University of Massachusetts, Amherst, September 2010

“The RoadRunner Dynamic Analysis Framework for Multithreaded Programs”
ACM Workshop on Program Analysis for Software Tools and Engineering
Toronto, Canada, June 2010
Brent Heeringa

“A Data Structure for Dynamic Partial Orders”
Invited talk at Boston University Theory Seminar

“Approximating Optimal Binary Decision Trees”
Invited talk at Alcatel-Lucent Bell Laboratories
Invited talk at Oregon State University
Invited talk at the University of Minnesota, Twin Cities
Invited panel discussion on graduate school at the University of Massachusetts
Morgan McGuire

“Image Space Photon Mapping”
Rensselaer Polytechnic Institute, Troy, NY, Dec. 3, 2009
University of Massachusetts at Amherst, Amherst, MA, Nov. 17, 2009
University of Pittsburgh, Pittsburgh, PA, Feb. 16, 2010
University of Maryland-Baltimore County, Baltimore, MD, Feb. 18, 2010
University of Maryland, College Park, MD, Feb. 22, 2010