Question 4 [14 marks]
In problem set 1 and test 1, you investigated different ways to reason about time zone compatibility
in this class. There is another aspect of time zone compatibility that we have not considered yet,
which is within the lecture breakout rooms held over Zoom. Suppose that each breakout room in any
given lecture hosts exactly 4 students and that the time zones of students in it are represented with
the quadruple (A, B, C, D). Two rooms are considered the same if they host the same time zones
regardless of order. For example, (“EST”, “CST”, “PST”, “JST”) is the same as (“PST”,
“JST”, “EST”, “CST”), (“CST”, “EST”, “JST”, “PST”), or any of the 21 other
permutations of that quadruple.
Now assume that after each lecture, Zoom generates a file where each of the n lines contains one
of the quadruples described above – one per breakout room. If students were sent to breakout rooms
more than once during a lecture, they go to the same room so the file has ultimately one line per room.
Your task is to design a program Unique Rooms which takes an array-representation of the file, and
returns an array containing one representation for each of the unique quadruples. The representation
for each quadruple in the output array does not have to be one of the original representations that
appears in the input array. The order of the quadruples in the output array also doesn’t matter. For
example, if Q is the input array, then A and B are two of several possible valid outputs (you should
only return one):
Q = [(“EST”, “PST”, “EST”, “NT”),
(“JST”, “BST”, “BST”, “CST”),
(“NT”, “EST”, “EST”, “PST”),
(“EST”, “NT”, “EST”, “PST”),
(“HST”, “CST”, “SAST”, “JST”)
(“SAST”, “CST”, “HST”, “JST”)]
A = [(“EST”, “PST”, “EST”, “NT”),
(“HST”, “CST”, “SAST”, “JST”),
(“JST”, “BST”, “BST”, “CST”)]
B = [(“CST”, “JST”, “HST”, “SAST”),
(“EST”, “EST”, “NT”, “PST”),
(“BST”, “BST”, “CST”, “JST”)]
(a) Give a one-sentence description for a naive algorithm for Unique Rooms which takes Θ(n2)
time.
(b) Describe (in plain English) an algorithm to implement Unique Rooms in worst-case Θ(n log n)
time. Explain the necessary implementation details.
(c) Justify the complexity of your algorithm for part (b).
(d) Suppose that we add the constraint that the representation of each quadruple in the output
array must be one of the representations that appeared in the input array. Now output A is
still valid, but Output B is not. Design an algorithm and supporting data structure to
implement Unique Rooms in O(n) expected time. For this algorithm, provide ALL necessary
implementation details. You may re-use implementation details we covered in class but make
sure to adapt them to your specific algorithm.
(e) Justify the complexity of your O(n) algorithm. Make sure to reference any assumptions you
made in the previous parts to justify that.
1