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 4 Algorithm Design [10 marks]
Assume that we have two arrays: CSC263 tz and CSC148 tz. The first array is of length n and
the second of length m. Each array contains the time zones of students from that class but without
duplicates. For example, if CSC263 contains 2 students from “PST”, and 3 students from “EST”, then
CSC263 tz = [“PST”, “EST”]. We would like to know if the time zones in our class constitute a
subset of the CSC148 time zones (the order of the subset elements doesn’t matter). For each part below,
state your solution in no more than one paragraph, and DO NOT write any pseudocode. Make
sure to state all necessary implementation details and assumptions for the data structures
that you use. Do not make any assumptions about the values of m or n (for example that m > n). It
is true that our class has fewer students than CSC148 but that doesn’t guarantee that we have fewer
time zones!
(a) First, assume that CSC148 tz is sorted (CSC263 tz may or may not be sorted). Give an
algorithm that will determine if there is a subset or not in worst case Θ(n logm). It must use the
least amount of space possible. In one sentence, justify that your algorithm runs in O(n logm)
worst-case time.
(b) Now assume that both CSC148 tz and CSC263 tz are unsorted. Give an algorithm that will
run in O(n + m) expected time using the least amount of space possible. Briefly justify that
your algorithm runs in O(n+m) expected time. HINT: what data structure have we seen in this
course that finds collisions across data?
(c) Explain how you could adapt your approach from part (b) to work if CSC263 tz and
CSC148 tz contain duplicate elements. So if:
CSC263 tz = [“EST”, “PST”, “CST”, “EST”] and
CSC148 tz = [“PST”, “CST”, “EST”, “NZL”, “EST”]
Then your algorithm must return True. But if:
CSC263 tz = [“PST”, “PST”, “CST”, “EST”] and
CSC148 tz = [“CST”, “EST”, “PST”, “NZL”]
Then it should return False. The adaptation should not increase the asymptotic runtime. HINT:
what would you augment your data structure from part (b) with?
There are 4 other questions in this test.
Remember that you must submit your aid sheet along with your answers.