COMP 2080 Summer 2022 – Assignment 9
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP 2080 Summer 2022 – Assignment 9
Questions
1. Assume that the function random(n) returns an integer selected uniformly randomly from the set {1, 2, 3, . . . , n}. For example, random(4) would return either 1, 2, 3 or 4, with equal probability.
Here is some code that uses random selections.
1 x 仁 random(10)
2 y 仁 random(10)
3 z 仁 random(20)
4 w 仁 random(30)
5 countStuff 仁 0
6 if ((x <= y) A (x != z))
7 countStuff 仁 countStuff+1
8 if ((x <= y) A (x != w))
9 countStuff 仁 countStuff+1
In the following questions, you must evaluate any summation notation, but you can leave your answer as an unsimplified numerical expression. Sample answer: 
(10)(20).
(a) [1 mark] How many distinct combinations of (x, y, z, w) are there in total? Note that
(x, y, z, w) = (1, 1, 1, 2) is distinct from (x, y, z, w) = (2, 1, 1, 1), etc.
(b) In each of the following questions, provide a counting argument to justify your answer.
A suggestion: for each x, determine how many possible values of y , z and w there are, then sum the result over x.
How many distinct combinations of (x, y, z, w) are there such that...
(i) [1 mark] x > y?
(ii) [1 mark] x s y and z = x and w = x?
(iii) [1 mark] x s y and z = x and w 
x?
(iv) [1 mark] x s y and z 
x and w = x?
(v) [1 mark] x s y and z 
x and w 
x?
(c) In each of the following questions, clearly state which conditions on x, y , z and w give rise to the value of countStuff under consideration. Then use your answers to parts (a) and (b) to complete the calculation.
After the given code runs one time, what is the probability that...
(i) [2 marks] countStuff= 0?
(ii) [2 marks] countStuff= 1?
(iii) [2 marks] countStuff= 2?
(d) [1 mark] Let C be the random variable that represents the value of countStuff after the given code runs one time. What is E(C), the expected value of C?
2. I have written an absolutely terrible algorithm for sorting an array. Assume that A is an int array of length n > 1. Further assume that all of the entries in A are distinct.
1 // pre: (A .length >= 1) A (entries in A are all distinct)
2 terribleSort(int[] A)
3 while (!sorted(A))
4 shuffle(A)
5 // post: A is sorted in ascending order
In this code, the function sorted(A) returns true if A is sorted in ascending order, and false otherwise. The function shuffle(A) randomizes the order of the entries in A.
(a) [1 mark] After shuffle(A) is called once, what is the probability that A is sorted in
ascending order?
To simplify notation, define p = 
.
(b) Assume that the entries in A could initially be in any order, with equal probability. (For
example, A was shuffled before it was passed to terribleSort().) Let us count the number of times the while loop condition in line 3 is checked before terribleSort() terminates.
In terms of p, what is the probability that the while loop condition is checked...
(i) [1 mark] Exactly 1 time? (That is, A is already sorted when it is passed to terribleSort().)
(ii) [1 mark] Exactly 2 times?
(iii) [1 mark] Exactly 3 times?
(iv) [1 mark] Exactly j times, where j > 1?
(c) [3 marks] Let N be the random variable that represents the number of times the while loop condition in line 3 is checked before terribleSort() terminates. The formula for
E(N), the expected value of N , is an infinite sum. Write down this sum, then evaluate it and show that the answer is E(N) = n!.
Useful identity. For any r, 0 < r < 1,
o jrj = r
Note that you will probably have to do a small amount of algebra before you can apply this identity to your expression for E(N)
3. I have also written a pretty terrible algorithm for adding two numbers.
1 // pre: a,b >= 1
2 terribleAdd(int a, int b)
3 c 仁 random(2)
4 if (c == 1)
5 answer 仁 a+b
6 else
7 answer 仁 a
8 n 仁 random(b)
9 j 仁 1
10 while (j <= n)
11 answer 仁 answer+1
12 j 仁 j+1
13 return answer
Recall the definition of random() that was given in Question 1: random(n) returns a uniformly randomly selected integer from the set {1, 2, . . . , n}. You can assume that any call to random() is an O(1) operation.
(a) [2 marks] Given the inputs a and b, the correct answer is the sum a + b. In terms of
b, what is the probability that terribleSum(a,b) returns the correct answer?
(b) [2 marks] Let X be a random variable that represents the return value of terribleSum(a,b).
In terms of a and b, what is E(X), the expected value of X?
(c) [2 marks] Let T be a random variable that represents the number of steps required by terribleSum(a,b). In terms of b, what is E(T), the expected value of T? You can approximate a h”ed number of steps by 1. However, note that a number of steps is not fixed if it depends on the result of a random selection.
2022-08-13