Overworked and over-caffeinated, the Teaching Assistant\'s (TA\'s) decide to ous
ID: 3110648 • Letter: O
Question
Overworked and over-caffeinated, the Teaching Assistant's (TA's) decide to oust the lecturer and teach their own recitations. They will run a recitation session at 4 different times in the same room. There are exactly 20 chairs to which a student can be assigned in each recitation. Each student has provided the TA's with a list of the recitation sessions her schedule allows and no student's schedule conflicts with all 4 sessions. The TA's must assign each student to a chair during recitation at a time she can attend, if such an assignment is possible. Describe how to model this situation as a matching problem. Be sure to specify what the vertices/edges should be and briefly describe how a matching would determine seat assignments for each student in a recitation that does not conflict with his schedule. This is a modeling problem -you need not determine whether a match is always possible.Explanation / Answer
The vertices consists of students and (chair,session) as pairs.
If we consider the pair (4,3) means chair 4 in session 3.
There is an edge from a student to a (chair, session) pair (i,j) iff the student is free during session j.
A matching would associated with each student is unique pair.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.