Advanced Algorithms COMP4121, Term 3 of 2020 FINAL
Submit your typed or CLEARLY WRITTEN scanned answers by email to 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. Assumethatyoudrawindependentlyanduniformlyrandomlynpointsx1,…,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 nk=1 |xk| of lengths of the corresponding vectors satisfies
n > |xk| > n − 2 ln n (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)