Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

January/February 2021 Examination period

FACULTY OF ENGINEERING

Third Year Examination for the Degree of

BacheIor and Master of Engineering and BacheIor of Science

COMS30042

Advanced AIgorithms

TIME ALLOWED:

2 Hours

Q1 .   (a)  consider an array of n integers whose values are in the range 0, . . . , u - 1. Give an algorithm that can sort the array in O(n log log u) time.

SoIution: Make a van  Emde  Boas  tree from the  integers taking  O(n log log u) time.   ln  linear time ind the largest element and call predecessor and delete re- peatedly to get the array in reverse order, then reverse.  or we can ind the smallest element and call successor repeatedly.

[3 marks]

(b)  State the space usage of the FKS hashing scheme and state the time complexity of the construction.

SoIution: Linear for both.

[2 marks]

Q2 .  Answer the following questions about Bloom ilters which we use to represent a set of elements.  Bloom ilters do  not support deletions natively.  However, your friend  Martha suggests a way round this problem.  Her idea is as follows.  create two Bloom ilters, one called 反add  and one callld 反de/ .  whenever we want to add an element e to the set we set the relevant places in 反add  to 1.  whenever we want to delete an element e we set the relevant places in  反de/  to 1.  ln order to check if an element is in the set we have to look at both 反add  and 反de/ .  First check 反add .  lf it  returns false then e  is not in the set.  lf it  returns true then check 反de/ .  lf this returns true then e is not in the set.  lf it returns false then e is in the set.

(a)  Does Martha，s idea give us the desirable property that false positives may occur but false negatives are impossible.  lf you think yes then explain why and  if no, give an example that breaks this property.

SoIution: You  can  have  false  positives  even  if  for  example  you  haven，t  deleted anything. You can also have false negatives by having a false positive in 反de/ .

[5 marks]

(b)  what is the time complexity of a lookup using Martha，s idea?

SoIution: lf the Bloom ilter uses r hash functions then it is O(r) time because we need to do r hash function calls twice.

[5 marks]

(c)  Another way to handle deletions is to store an m-bit number in the array positions. ln practice it turns out that 4 bits normally suices.  Describe how insert, delete and lookup queries could be supported in such an extended Bloom ilter.

SoIution: The  insert operation then increments the values at the relevant places by 1 and the delete operation decrements the value of each of the locations by 1. A lookup checks to see if all the values at the relevant locations equal 0.

[5 marks]

(d)  Does  your solution using  m-bit numbers in the array positions have the desirable property that false positives may occur but false negatives are impossible?  lf you think yes then explain why and if no, give an example that breaks this property.

SoIution: No.  lf we insert x and y which have the same hash locations and then delete y twice and then query x we will get a false negative.

[5 marks]

(e)  lmagine we want to use a Bloom ilter of size 800 bits for a web cache which stores

up to 100 URLs picked from a universe of 1000000 URLs.  How would you calculate the optimal number of hash functions to use to minimise the false positive probability and what false positive probability does it give? You can give the probability to one decimal place.

SoIution: The  number of hash functions  is 800/(100e) 个 2.9.   ln  practice you should round this up to 3. The false positive probability is 心 0.05

[5 marks]

Q3 . A hash function family H = {h1 , h2 , . . . } with hi  : U 一 T is pairwise independent if for randomly and uniformly chosen h e H, we have that for any distinct x, y e U and pair of values u, Ⅴ e T , pr(h(x) = u V h(y) = Ⅴ ) = 1/|T | 2 .

Let x1 , . . . , xn  be diferent values chosen from U.

(a)  pick at random a1 , . . . , an  e {0, 1} and deine

ha1 ,...,an (x1 , . . . , xn ) = a1x1 + . . . + anxn  mod 2

prove that this family is pairwise independent or give a counter-example.

SoIution:

This is not pairwise independent.  consider the zero string input x1  = x2  = . . . = xn  = 0.  lt always maps to zero and any other string will map to zero with probability 1/2 .  Hence the probability they are equal is 1/2 not 1/4 .

[5 marks]

(b)  pick at random ao , . . . , an  e {0, 1} and deine

hao ,...,an (x1 , . . . , xn ) = ao + a1x1 + . . . + anxn  mod 2

Let u = u1 , . . . , un  and Ⅴ =  Ⅴ1 , . . . , Ⅴn .  ui  and Ⅴi  must difer at at least one index i and we can ignore all other indices.  we can regard a1 , . . . , an  as selecting a subset of values in the two inputs u and Ⅴ.  You can assume without proof that the probability of the size of the subset of mismatching indices being even or odd size is equal.

prove that this hash function family is pairwise independent.

[5 marks]