CS计算机代考程序代写 CSC263H1 Summer 2021 Term Test 1

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.