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 5 Heaps [7 marks]
In problem set 1, you calculated the probability that a randomly generated array of size 28 constitutes
a valid heap. The probability turned out to be very, very small. In this question, you will do almost
the same but on a much smaller array and without consulting an external source. Suppose that H is
a random permutation of the array [34, 77, 2, 15, 6, 90] where every permutation is equally
likely. We are interested in calculating the probability that H represents a valid heap. Let’s do this in
steps:
(a) How many different permutations of the values of H are possible??
(b) If H represents a min-heap, which value has to appear in the first element of H?
(c) How many different permutations of H represent valid min-heaps? Explain your reasoning using
plain English or diagrams. You are NOT allowed to consult http://oeis.org as you did in the
problem set.
(d) How many different permutations of H represent valid max-heaps? HINT: for this part, you do
not need to re-do all the work you did in part (c).
(e) What is the probability that H holds either a valid max-heap OR a valid min-heap? You do not
need to simplify the fraction.
There are 4 other questions in this test.
Remember that you must submit your aid sheet along with your answers.