Description
-
Submission guidelines:
-
Assignments should be uploaded to Connex->Assignments. You can write your solutions using a text editor and upload the PDF file or you can write it by hand and take a CLEAR
photo or scan it, and then upload it.
-
Include your V number and your name as it appears on Connex Roster, otherwise, the TAs may not be able to enter your grades.
-
-
Due date is Monday October 15th 3:30 pm. Late assignments are not accepted.
-
-
[10 marks] For the following recurrence, prove using the substitution method (i.e. induction) that
= (2‘). You can assume that ) = 1, and the exact form of induction is 
≤ 2‘.
-
=
1
if = 1
−1 +2‘
if > 1
Note that you should also show for what values of constant c this inequality holds just like any other Big-O proof.
-
[20 marks] Assume that we have a binary heap that we are representing as a 0-based index array. (Similar to the binary heap in class with the difference that indices start from 0). Use these three methods below to answer to parts (a) and (b):
Parent(i)
Left(i)
Right(i)
return
( − 1)/2 
return 2 + 1
return 2 + 2
a) Write a recursive pseudocode for a method called Print-Grandparents(i). For a given
index i, this method prints i, then parent-of-parent of i, and so on.
For example, on the following heap Print-Grandparents(15) outputs “2 18 23”. Also, Print-Grandparents(8) outputs “6 21”.
-
Write a pseudocode for a method called Print-Aunt(i). For a given index i, this method prints the sibling of the node’s parent.
For example, on the following heap Print-Aunt(5) outputs 21, and Print-Aunt(7) outputs 14.
-
[5 marks] Say we have balls numbered from 1 to , and we have bins numbered from 1 to . We are throwing these balls one by one into the bins. When we throw a ball, it goes with equal probability of 1/ into any of the bins.
What is the expected number of balls in bin number 1 after throwing all balls into the bins? Hint: This problem is very easy if we define the random variables as follows. Assume that random variable Y represents answer which is the number of balls in bin 1. Also, assume that for each ball we have a random variable 7. 7 is 1 if the ball goes to bin 1 and is 0 otherwise. So, we can say that = 9 + : + … + <, because basically for each ball that goes into bin 1 we are adding 1 to the value of Y.
Now, compute [ 7] for each i, and then compute [ ] using linearity of expectation.
-
[15 marks] For each of the following recurrences say which case of the Master method it falls into, and then write the solution to the recurrence.
-
2
/16
+ ).:B -
8
/2
+ Θ( :)
-
27
/3
+ G log
