Advisor: David Liben-Nowell
Suppose you decide to organize all the CS majors to go out for dinner
during week 6. The website doodle.com
has made an important part of the coordination problem much simpler:
someone sends out a link, and each of you enters the nights that
you're free, and Doodle organizes your responses on a single grid.
But the task of actually choosing a night falls to the initiator of
the poll. And, although this dinner problem seems easy (just pick the
day that the set of free people is largest!), there are more
computationally difficult variations. Only some of the majors have
cars; you need to make sure that there are enough seats for everyone
to go. Different people prefer Thai, sushi, nouveau american,
vertical food; you should maximize the collective happiness of the
group when you pick a restaurant and a date.
In this comps project, you'll build a "Carleton scheduling service": a
general, flexible, and easy-to-use tool to solve a variety of
scheduling problems of this type. You will begin with some of the
simplest scheduling tasks, such as the basic dinner problem above, and
the development of a functional, aesthetic, and usable interface for
scheduling. Once you've solved these basic problems, you'll move on
to more complicated problems, with different types of data,
constraints, and objectives, and an improved interface, allowing more
"administrator" control of various features of the system. The target
audience for this project will be "client" users from across campus,
so in addition to the back-end scheduling code, you will also need to
spend serious effort on developing a useable system for people who
have never heard of words like "algorithm", "feasible", or "bipartite".
II. THE PROJECT
Your system should eventually support scheduling capabilities for some
of the following "clients" on campus:
- the Carleton Summer Science Institute and Summer Writing Program
(assigning students to classes and multiple discussion groups based
on student preferences for topics and programmatic preferences that
different groups be gender balanced and overlap as little as possible);
- the Career Center (matching students to alums/employers/timeslots
for "speed networking" or interview slots); and
- the music department (matching students taking private music
lessons to teachers and timeslots, according to lists of free time
for students and faculty and faculty preferences for the shape of
- in a very meta twist: scheduling your own comps oral exams.
Your tasks broadly fall into two categories:
finding and implementing -- or designing and implementing -- for as
large a set of interesting types of scheduling problems as possible,
efficient algorithms to find optimal/feasible solutions. As a first
step, you'll need to implement a solution to weighted two-sided
matching problems (to include at least the dinner problem and the
simplest form of the instrumental lesson problem). This will be
algorithms-intensive piece of the project, and having a team in which
multiple members have taken CS 252 will be beneficial.
designing and implementing an interface to your system. As a first
step, you'll need to allow the configuration of a new problem instance
by an administrator (what data do users input? what's the objective
that's supposed to be optimized?), entering of data by individual
users, and the computing of a solution by an administrator. You
should eventually allow the administrator to do a "bulk import" of
data, users to change their data, the administrator to try to force a
portion of the solution to have a certain form (try to assign DLN to
the 3:00p timeslot, e.g.), etc. One important part of the interface
is a capacity for the administrator to reject a solution proposed by
the system because it violates some constraint previously unknown to
the administrator, who then enters it and recomputes a solution.
David Karger, Cliff Stein, Joel Wein. Scheduling
Algorithms. CRC Handbook on Algorithms, 1997.
Assignment problems: A golden anniversary survey.
European Journal of Operational Research.
Volume 176, Issue 2, 16 January 2007, Pages 774-793.
Steven J. Miller.
An Introduction to Linear Programming.
Tom Cormen, Charles Leisersen, Ron Rivest, and Cliff Stein.
Introduction to Algorithms.
Jon Kleinberg and Eva Tardos.
Coin-LP (a linear programming solver)