COMPUTER SCIENCE TRIPOS Part IA – 2022 – Paper 1
Algorithms 2 (djw1005)
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 programme, 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]
[You may use standard algorithms and results about them provided you state them
clearly.]