Question

Design an algorithm that minimises Ccmp, the number of comparisons of two books’ labels in the alphabetical order, and Cmov, 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 arenbooks on the main shelf, which haveal ready 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 ascending alphabetical order and you are allowed to use a temporary shelf of an infinite capacity. Design an algorithm (description + pseudo code) for the robot to arrange the new books onto themain shelf using Ccmp=Θ(n+m) label comparisons and Cmov=Θ(n+m) book movements in the worst case. 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 WITH YOUR 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 ton, for instance,m=10. Design an algorithm (description + pseudo code) for the robot to arrange the new books onto the main shelf using Ccmp=Θ(log(n)) label comparisonsin the worst case. 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

//COMPLETE WITH YOUR PSEUDO CODE HERE

P/s: I have already posted this question, but haven't received a useful idea for it. So, please help me with a useful idea and more detailed pseudocode.

Answer 1

So in above question

ccmp = minimum number of comparision of two books

cmov = number of book movement (one movement is counted whenever a book is moved from one location to another)

A = main(n book initially in  array) , B = portable(m book initially in array ) ,c temporary

1.) so in the first part of question given that array A and B both are sorted , to obtain final sorted result we will use concept of merging two sorted array ----

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 wihle loop until any of one A or B is empty.

if(A[i]<=B[i]) then in this case we will insert A[i] in temporary and i++(move one step in A array because A[i] is inserted in C array )

if(A[i]>B[i]) then in this case we will insert B[i] in temporary and j++(move one step in B array because B[j] is inserted in C array )

----after book in any of array is finished we will simplly append books of other array to C array.

void ArrangeBookScenario(A,B,C,n,m) 
{ 
    int i = 0, j = 0, k = 0; 
  
    // Traverse both array 
    while (i<n && j <m) 
    { 
 
         //inserting the book first which is lexographical smaller in order 
        if (A[i] <= B[j]) 
            C[k++] = A[i++]; 
        else
            C[k++] = B[j++]; 
    } 
  //simply appending remaining array element in case one of the array is empty
    while (i < n) 
        C[k++] = A[i++]; 
  
   
    while (j <m) 
        C[k++] = B[j++]; 

 A = C //putting books of temporary cell in main shelf
} 

2.) In This siuation first array is sorted but second is not so we will use binary search concept . we will find upper_bound(first element in array greater than given element ) for each element in array B and insert that element at index of upper_bound. after shifting array to right.

complexity o(m*logn)

//as we know in worst case binary search takes logn comparision so total comparison will be m*logn(as we are applying binary search for each elemenrt of B). ccmp = logn//because m <<< n given in question

example of worst case

//lets take a scenario that element of B are also sorted and less than every element of A so upper_bound will be first element itself so we have to shift whole array A to right .

Algo for above problem

Algorithm ArrangingBooksScenario2(A,B,n,m)
{
for(int i=0;i<B;i++)
{
int index = upper_bound(A,B[i]); //binary search based upper_bound function that will return first position where A > b[i]
 
  shiftarray(index);//shift content of array by 1 position to right from index till end of array
  A[index] = B[i]; 
}
}