Question

Your developing a set of algorithms for a librarian robot that can put newly arrived books to the main book shelf (of a sufficient capacity) while maintaining an alphabetical order.

Design an algorithm that minimises C_cmp, the number of comparisons of two books’ labels in the alphabetical order, and C_mov, the number of book movements (one movement is counted whenever a book is moved from one location to another) in the worst case. Suppose there are n books on the main shelf, which have already been sorted in an ascending alphabetical order. The m newly arrived books are carried into the library on a portable shelf.

a) Scenario 1: The newly arrived books have also been sorted in an ascend- ing alphabetical order and you are allowed to use a temporary shelf of an infinite capacity.

i) Design an algorithm (description + pseudo code) for the robot to arrange the new books onto the main shelf using Ccmp = Θ(n + m) label comparisons and Cmov = Θ(n + m) book movements in the worst case.

ii) Explain why your algorithm has the stated worst case complexity (ignoring the constant and choosing the dominant term in your analysis).

Algorithm ArrangingBooksScenario1(A,B,C,n,m)

//A, B, and C represent the arrays of book labels for the main, the portable, and the temporary shelves
//COMPLETE PSEUDO CODE HERE

b)Scenario 2: There is no temporary shelf to use in the library and the number of newly arrived books, m, is a small constant compared to n, for instance, m = 10.

i) Design an algorithm (description + pseudo code) for the robot to arrange the new books onto the main shelf using Ccmp = Θ(log(n)) label comparisons in the worst case.

ii) What is the number of book movements Cmov incurred in the worst-case of your algorithm and why?

Algorithm ArrangingBooksScenario2(A,B,n,m)
//A and B represent the arrays of book labels for the main and the portable shelves

//PSEUDO CODE HERE

Answer 1

1.) Given that both of A and B are sorted we can using following standard approach.

i) we take i=0 and j=0 , k=0 pointing to stating index of array A ,B and C respectively we will use a while loop and keep inserting minimum element among A[i] and B[j] in array C until we reach end of any of the array.

if(A[i]<=B[i]){

C[k] = A[i];

i++;

k++;
}

else{

C[k] = B[j];

j++;

k++;

}

As per the algo we can see that for each element at max 1 time we can change position so  Cmov = Θ(n + m).

and similiarly at max n+m time we can compare content of array A with content of B array so .Ccmp = Θ(n + m).

finally we will put content(books ) of c to main shelf(A).

void ArrangeBookScenario(A,B,C,n,m) 
{ 
    int i = 0, j = 0, k = 0; 
  
    // Traverse both array 
    while (i<n && j <m) 
    { 
 
        if (A[i] <= B[j]) 
            C[k++] = A[i++]; 
        else
            C[k++] = B[j++]; 
    } 
   append(A,C); //append remaining elements of array A to C
   append(B,C); //append remaining elements of array B to C
 A = C //putting books of temporary cell in main shelf
} 

2.) In this problem we are given that Array A is sored and the array B is not. and size of array B is small comparision to array A so we can using binary search based approach here. we will be finding appropriate index for insertion of each element of B aray and shifting remaining content of array .

upper bound function can help us to find proper index .

upper bound(a,x) tells us the first index in array a where A[i] > x. we will insert x at position returned by upper bound and will push array to right by 1 unit.

Algo for above problem

As upper bound is an algo based on binary search so in worst case comparision taken will be logn.

So Ccmp = m*logn = O(logn)

and

Cmov at worse case can be upto O(n*m)

Take scenario when Array B is also sorted but in reverse order that will give us max possible value of Movements in Array,

Algorithm ArrangingBooksScenario2(A,B,n,m)
{
for(every element  x in B )
{
int index = upper_bound(A,x); // upperbound will tell index of first element  in a where A[i]> x 
  shiftarray(index);//shift content of array by by 1unit from index till last 
  A[index] = B[i]; 
}
}