Question 3 [15 marks]
You have just been hired as a work study at UofT this summer to implement a new MarkUs feature.
The feature pairs students into groups for projects and problem sets such that both partners are in
the same time zone. But you discover that you are too busy with CSC263 to find a sophisticated way
to implement this feature. So instead, you write a few lines of code that randomly pair all students
from the class list into 2-person groups (you can assume that the total number of students in any class
is even), and then check if their parings are time zone compatible using the following subroutine:
def TimeZoneCompatible(pairs): #pairs is a list of ordered pairs of
student IDs
1. for i in range length(pairs):
2. t1 = getTimeZone(pairs[i][0])
3. t2 = getTimeZone(pairs[i][1])
4. if t1 != t2:
5. return False
6. return True
If at least one pair has partners from two different time zones and TimeZoneCompatible
returns False, you plan to randomly re-pair everyone, perform the time zone check, and repeat until
TimeZoneCompatible returns True. Your analysis below will help us determine how terrible (or
not) this lazy implementation idea is. Note that getTimeZone in this question has nothing to do
with the one from Q1 of the problem set.
1. What operation or operations would you count for the runtime analysis of
TimeZoneCompatible? Make sure to state the line number(s). What does the size of input
(n) refer to in this question?
2. Perform a best-case and worst-case analysis of TimeZoneCompatible based on the
operation(s) you specified in part 1. Justify your answer and ensure it’s a tight asymptotic
bound.
3. Perform an average-case analysis on TimeZoneCompatible. Use p to denote the probability
that a pair at each point in the pairs list contains an across time zone partnership (i.e. the
partners come from two different time zones). To simplify the analysis, you may assume that the
probability of an across time zone pairing is independent of its position in the list, independent
of the other values in the list, and that there is a valid pairing for all students. Give exact counts
and probabilities in terms of n and p (not simply an asymptotic expression).
4. Let’s now look specifically at one possible pairs list that your algorithm has generated randomly
from the Summer 2021 CSC263 classlist. Find the specific value of n and p by using the fictional
data that our class in total has 84 students in EST, 10 in PST, 20 in CST, 4 in PKT, and 8 in
SAST. Show your work and round the answer to three decimal places. Make the same assumption
about probability independence as in part 3. It is necessary to note here that the outcome of the
second call to getTimeZone (on line 3) is not independent from the outcome of the first call.
5. Using the values of n and p that you found in the previous part, what is the expected number
of comparisons it would take TimeZoneCompatible to determine if a randomly generated
Summer CSC263 pairs list has an incompatible pair? Show your work and round the answer to
three decimal places.
6. Using the probability assumptions from part 3 (i.e. independence of list values) and the value
of p you found in part 4, state the exact probability that your random pairing generator will
produce a partners’ list with the required time-zone compatibility for our class. You can write
the probability using the scientific notation explained in Q4 of this problem set. In 2-3 sentences,
state your opinion about the efficiency of this lazy pairing approach.
4