Project 1 Specification
22 May 2001


The goal of this project is to develop—through experience—your ability to:

The Resource-Allocation Problem

Resource allocation is an often-difficult, real-world problem. One version of the problem is the personnel allocation problem: you have people with various qualifications and preferences, jobs with various requirements and preferences, and a need to assign the people to the jobs intelligently.

One such problem is the assignment of TAs to subjects. In its simplest form, you can imagine a set of subjects, each of which requires one TA, and a set of potential TAs, each of which can be assigned to zero or one subject.

You could think of this as a search problem, with depth s and branching factor t. You could think of solving the search problem by doing a British Museum search; that is, you could generate all possible paths and then evaluate each. Alas, even with just 10 subjects and 15 TA candidates, a British-Museum enumeration of assignments unthinkable, which you should show yourself, if in doubt, on the back of an envelope.

What you start with

Accordingly, you will need to do some other sort of search. We provide you with a starting point in the form of a program cum data set and rule set with the following characteristics:

Your job

We provide you with a set of subject and TA descriptions. In particular, you are to do the following:

You may be able to find a solution for the sample data by hand. Keep in mind that the goal is not only to find a solution for the sample data, but also to write a program that can handle similar problems, of approximately the same number of TAs and subjects, with, for example, other, more, or fewer preferences and requirements.

Also, your program is to scale, for example, to ten times more TAs and subjects.

Important Notes