Goals

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

• Make technical choices.
• Bring multiple ideas together to solve a problem.
• See how one problem can serve as a precedent for the solution of another.
• Deal with problems that have less specification than that typical of a problem set.
• Organize and perform work with a partner.
• Write about your work.

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:

• The search done is depth-first search.
• Node expansion is done by a rule-based system.
• There is sample database of a few assertions and one sample rule.
• The assumption is that no subject requires more than one TA.

Your job

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

• Develop a set of assertions from the subject and TA descriptions. You must decide what to make use of in the descriptions and what to ignore: we expect you to capture some details of description only approximately or not at all.
• Develop a set of rules using commonsense and the subject and TA descriptions.
• Choose and implement a search strategy.
• Choose and implement a mechanism for determining the quality of a particular TA assignment.

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

• Your program is to distinguish between requirements and preferences: requirements cannot be violated; preferences can be, but the quality of a set of TA assignments declines in proportion to the number and sign of violated preferences.
• Your program is to do the best it can with more TAs than TA assignments, just the right number, or not enough TAs for the available TA assignments.
• You are to assume each subject has a requirement for just one TA. We will ask you to comment on what you would need to do to generalize to multiple TAs per subject.