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