Let M[1 ... n, 1...n] be an n times n matrix in which every row and every column

Question

Let M[1 ... n, 1...n] be an n times n matrix in which every row and every column is sorted. Such a matrix is called totally monotone. No two elements of M are equal. (a) Describe and analyze an algorithm to solve the following problem in O(n) time: Given indices i, j, i', j' as input, compute the number of elements of M smaller than M[i, j] and larger than M[i', j']. (b) Describe and analyze an algorithm to solve the following problem in O(n) time: Given indices i, j, i', j' as input, return an element of M chosen uniformly at random from the elements smaller than M[i, j] and larger than M[i', j']. Assume the requested range is always non-empty, and that you have a random number generator that returns a uniformly random integer in a specified range. (c) Describe and analyze a randomized algorithm to compute the median element of M in O(n log n) expected time.

Explanation / Answer

a)

function [n m] = NumElements (A,i,j,k,l)
#Inputs are:
#A is a nxn Matriz totally monotone
#i,j,k,l are index
#n number of elements smaller than A[i,j]
#m number of elements greater than A[k,l]

aux1=A(i,j);
aux2=A(k,l);

n=0;
m=0;

[r c]=size(A);

for(z = 1:r)
for(w = 1:c)
if(A(z,w)<aux1)
n=n+1;
endif
if(A(z,w)>aux2)
m=m+1;
endif
endfor
endfor
endfunction

b)

function [num] = RandElement (A,i,j,k,l)
#Inputs are:
#A is a nxn Matriz totally monotone
#i,j,k,l are index
#n number of elements smaller than A[i,j]
#m number of elements greater than A[k,l]

aux1=A(i,j);
aux2=A(k,l);

n=0;
m=0;
countvec=1;
#Initialize a vectorize
v=[];
[r c]=size(A);

for(z = 1:r)
for(w = 1:c)
if(A(z,w)<aux1)
n=n+1;
v(countvec)=A(z,w);
countvec=countvec+1;
endif
if(A(z,w)>aux2)
m=m+1;
v(countvec)=A(z,w);
countvec=countvec+1;
endif
endfor
endfor

#Return an element of M chosen uniformly at random
#from the elements smaller than A(i,j) and larger than A[k,l]

msize=numel(unique(v));
num=v(randperm(msize, 1));

endfunction

c)

function [medianA] = BinarySearch (A)

[n m]=size(A);
v=[]
count=1;

for(i=1:n)
for(j=1:n)
v(count)=A(i,j);
count=count+1;
endfor
endfor
v=sort(v);

msize=numel(unique(v));
ran_num=v(randperm(msize, 1));

index = 0;

for(i=1:msize)
if(vec(i)==ran_num)
index =i;
endif
endfor
mid=ceil(msize/2);

while index != mid
if index > mid
index = index -1;
else
index =index +1;
endif
endwhile

if index == mid
medianA=vec(index);
endif

endfunction

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.