In Part II of the Computer Science Tripos at Cambridge, students take two Units of Assessment (UA). Some UAs have a maximum capacity, set by the lecturer. Students are asked to shortlist three or more UAs, and the department tries to find class rosters such that each student is assigned two of the UAs they shortlisted.

(a) Give an efficient algorithm for finding such rosters, if they can be found. [5 marks]

(b) State an appropriate correctness property, and prove it. [7 marks]

(c) Derive the running time, in big-O notation, as a function of the number of students. Treat the number of courses as fixed. [3 marks]

Oxbridge Academy has a similar program, but larger: students are required to take three UAs, and they shortlist at least four. Some UAs are in Michaelmas term, others in Lent, and the Academy wishes to create class rosters such that no student has all three of their UAs in a single term.

(d) Modify your algorithm to accommodate this requirement. [5 marks]