Question

you are given a list of n bits {x1,x2,...,xn} with each xi being an element in {0,1}. you have to output either: a) a natural number k such that xk =1 or b) 0 if all bits are equal to zero. the only operation you are allowed to access the inputs is a function I(i,j) defined as:

I(i,j) = { 1 (if some bit in xi, xi+1,...,xj has vaue 1), or 0, (if all bits xi,xi+1,...,xj have value 0}.

the function I(.,.) runs in constant time.

design a divide and conquer algorithm. describe the algorithm in words. no pseudocode. state the recurrence relation.

Answer 1

We will first check the value of I(1,n). If it is 0, then we will return 0. But if it shows 1 as output, then we will divide the bits in two parts, with almost same number of elements (i.e. from 1 to [n/2] and from [n/2]+1 to n). Then, we will check the output of the function on these two parts of the bits (i.e. I(1,[n/2]) and I([n/2]+1,n)). Now, if only one of the outputs return 1, then we will take that array and divide it further and go on with the same process. If both of the arrays give us 1 as a output, then we will take the first one as the array and then we will go on with the same process.