CSC263H1 Summer 2021 Term Test 1
Submission Instructions
� You may type your answers or hand-write them legibly.
� You may submit your answers as a single document or as multiple documents.
� You may name your file(s) any way you want (there is no “required file” except for aidsheet.pdf).
� You may submit your answers in PDF or in photos (JPEG/JPG/PNG/GIF/HEIC/HEIF), but
NOT other formats (In particular, Word documents cannot be accepted – please export to
PDF before submitting.)
Question 2 Average Case Analysis [5 marks]
The Newfoundland Time Zone (NT) subtracts 3.5 hours from Coordinated Universal Time (UTC)
during standard time, and 2.5 hours during daylight saving time. Assume that we have a linked list L
with n elements. It stores the time zones of each of the students enrolled in CSC263. Each element in
L holds a string representing a time zone of a student. For unknown reasons, it is rare to find “NT”
in L (i.e. we hardly have students based in Newfoundland). Because of that, you can safely assume
that when searching for “NT” in L, there is at most one “NT” in L, and that it is equally likely to be
in any of the n positions or not in L at all. Consider the code below:
1. def hasNT(L):
2. j = L.head
3. while j != None and j.key != “NT”:
5. j = j.next
6. return
Perform the average case analysis on hasNT(L) using the assumptions stated above about L. Show
your work, justify each step, and try to simplify the math as much as you can. Use the comparisons
on line 3 as the operations of interest and make sure to give a tight asymptotic bound based on your
calculations. HINT: The average case analysis we did on hasTwentyOne(L) had only the assumption
that each element in L was equally likely to have the value we were looking for. Is this the case here?
There are 4 other questions in this test.
Remember that you must submit your aid sheet along with your answers.