COMS31900 Advanced Algorithms 2020
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
August/September 2O2O
Faculty of Engineering
Resit & Supplementary Examination for the Degrees
of
Bachelor of Science
Master of Engineering
COMS319OO(R)
Advanced Algorithms
TIME ALLOWED：
2 Hours
1. (a) (6 points) suppose that we use a Bloom ilter with a table of size n = 1oo and two completely random hash functions chosen from the set of all functions mapping the universe N to the domain [n]. suppose further that we have inserted exactly 3o distinct elements into the Bloom ilter.
we now execute MEMBER(k), for some element k E N that has not previously been inserted into the Bloom ilter. Let p be the probability that MEMBER(k) returns true. observe that p depends on the number of collisions in the Bloom ilter. what is the precise range of p？
A. 
B. 
C. 
D. 
E. none of the above
(b) (6 points) Consider a hash table of size m. suppose that we selected a completely random hash function h from the set of all functions mapping the universe N to the set [m]. suppose that we inserted m log m items into the hash table using the hash function h. what is the expected number of collisions (recall that a collision is a pair of inserted items that are mapped to the same location)？
A. Θ(1)
B. Θ(log m)
C. Θ(log2 m)
D. Θ(m)
E. Θ(mlog m)
F. Θ(m log2 m)
G. none of the above
2. (a) (6 points) Give one property of Bloom ilters that makes it superior to Cuckoo hashing.
(b) (6 points) Give one property of Cuckoo hashing that makes it superior to Bloom ilters.
(c) (6 points) Let H be a family of weakly-universal hash functions h with h : {o, . . . , u — 1} 一 {o, 1}. we now construct a family of hash functions ? with g : {o, . . . , u — 1} 一 {o, 1, 2, 3} as follows: For every pair of hash functions (h1 , h2 ) e H2 , we include the function h1 (①) + 2 . h2 (①) into ?. prove that ? is weakly universal.
(d) (6 points) Let H be a family of hash functions h with h : {o, . . . , u — 1} 一 {o, . . . , k — 1}. suppose that |H| = 1, i.e., H contains only a single hash function. Give an example for H that shows that if k > u then H is weakly universal. Further, prove that H is not weakly universal if k < u.
(e) (6 points) suppose that we are given a sequence of n instructions. what does it mean if each of these instructions has amoTtized e①pected runtime O(f (n))？ Furthermore, illustrate what this means in the context of Cuckoo hashing.
(f) (5 points) Let N be a universe of size u. what is the worst-case runtime of any operation that a van Emde Boas tree that is built on N supports？ No justiication needed.
(g) (5 points) what are the space requirements of the 2D orthogonal range searching data structure discussed in the lectures when it stores n distinct points？ Justify your answer very briely.
3. (6 points) Construct the Cartesian tree for the input 9, 3, 7, 1, 8, 12, 1o, 2o, 15, 18, 5.
4. (a) (6 points) Give the deinition of an FPTAS for an optimisation problem. You may give only the minimisation version.
(b) (6 points) Give the deinition of an APTAS for an optimisation problem. You may give only the minimisation version.
(c) (6 points) Give two diferences between an FPTAS and an APTAS.
5. consider the optimisation problem SUBSET SUM: Given a set S = {s1 , . . . , sm } of m integers and an integer t, ind the size of the largest subset of S which is no larger than t. Recall that the size of a set is the sum of its elements. Now look at the following partial algorithm for computing the exact answer:
(a) (6 points) what should be in place of the two blank spaces on lines 3 and 4？
(b) (6 points) what should be in place of the blank space on line 6？
(c) (6 points) what is the running time of this algorithm？ You should give the strongest worst case asymptotic running time possible.
(d) (6 points) Does this algorithm run in polynomial time？Give a brief justiication of your answer.
2023-08-09