A math department consisting of p faculty members, F1; F2; : : : ; Fp, will offer p
courses, C1;C2; : : : ;Cp, in the coming semester and each faculty member will teach exactly one course. Based on personal preferences, each faculty member names his or her first and second choices for a course.

A. We say that a course assignment is a feasible assignment if every faculty member teaches either their first or second choice course. Formulate the problem of finding a feasible assignment as a shortest path, max flow, or min-cost flow problem.

B. A feasible assignment is said to be k-feasible if it assigns at most k faculty members to their second choice course. Formulate the problem of finding a k-feasible assignment for any given k, as a shortest path, max flow, or min-cost flow problem.

C. We say that a feasible assignment is an optimal assignment if it maximizes the number of faculty members assigned to their first choice course. Formulate the problem of finding an optimal assignment as a shortest path, max flow, or min-cost flow problem.