Advanced Algorithms COMP4121, Term 3 of 2020
FINAL
Submit your typed or CLEARLY WRITTEN scanned answers by
email to .edu.au by December 9 at 9am. To email, use
ONLY your CSE email account. If you are scanning make sure your file
is less than 5MB, otherwise it might not go through. Needless to say, you
are not allowed to consult anyone and your answers will be checked for
plagiarism. If you have any questions email me and I will try to answer
them as promptly as I can. You can cite any result from class without
deriving it or proving it. Good luck!
1. Compute the probability that a SkipList with n elements has at least (log2 n)
2
many levels. (15 points)
2. Assume that in the deterministic algorithm for Order Statistic we split numbers
into groups of 2k + 1 many elements (so, the particular case we did in class is
for k = 2 because we split numbers into groups of 2 × 2 + 1 = 5 elements.)
Derive an estimate of the run time Tk(n) of the algorithm for general k and
show that Tk(n) satisfies Tk(n) ≤ 10Ck n for all k > 1 where Ck is a constant
such that the overhead of the recursion is bounded by Ck n. (20 points)
3. Assume that you draw independently and uniformly randomly n points x1, . . . , xn
from the unit ball in n dimensional space Rn. Show that with probability of at
least 1−3/(2n) it holds that the sum
∑n
k=1 |xk| of lengths of the corresponding
vectors satisfies
n >
n∑
k=1
|xk| > n− 2 lnn (15 points)
4. You happen to be a very good student receiving only Distinctions and High
Distinctions. To get a High Distinction you have to score between 85 and 100;
1
to receive a Distinction you have to score between 75 and 84. You noticed that
on average after each High Distinction in the next exam you received another
High Distinction in 2 out of every 3 cases, and after each Distinction you are
equally likely to get a High Distinction as you are likely to get a Distinction.
You also notice that whenever you get a Distinction all scores between 75 and
84 are equally likely, and similarly whenever you get a High Distinction it is
equally likely you got every score between 85 and 100. Estimate your average
mark. (15 points)
5. Use the PageRank algorithm to rank Twitter users according to their pop-
ularity. If a person A follows person B, person B is important to person A
proportionally to the number of times A retweets messages of person B plus
the number of times person A liked messages of person B. (15 points)
6. Explain in your own words why Spectral Clustering algorithm works for clusters
which are not center based. (20 points)
2