The CS department has received several applications for teaching assistant po$-$ sitions from its students. The applicants are provided with the list of available courses and asked to submit a list of their preferences. The TA committee at UTCS prepares a sorted list of the applicants $($according to the applicants$$ background and experience$)$ for each course and the total number of TAs needed for the course.

Note that there are more students than available TA spots. There can also be multiple TAs per course, though a single TA can only be assigned to $1$ course.

Making matter more complicated, certain applicant$-$course are disallowed since an applicant does not have enough background in a specific course.

We will say that A $($an applicant$)$ prefers C $($a course$)$ to C$$ iff C is ranked higher than C$$ on his$/$her preference list. The committee wants to apply an algorithm to produce stable

Problem $3$ continued on next page. $..$ Page $2$ of $3$

Assignment $1$ Problem $3($continued$)$

assignments such that each student is assigned to at most one course. The assignment of the TAs to courses is stable if none of the following situations arises.

$1.$ If an applicant A and a course C are allowed and not matched, but A prefers C more than his$/$her assigned course, and C prefers A more than, at least, one of the applicants assigned to it$.$

$2.$ If an applicant, A$,$ and a course, C$,$ are allowed such that A is unmatched, and C has an empty spot or an applicant A$$ assigned to it such that C prefers A to A$.$