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

Answer 1

For Scenario1:

Since all the previous books i.e. "n" are in sorted order and new books i.e. "m" are also sorted. We only need to compare one book of previous book with one book of new book.

So algorithm works as

Suppose n = 3 and books are ['ab','bdf',bgh']

m = 2 and books are ['ac','ef']

So our shelve C will be of size n+m = 5

Start iterating from starting of both Shelves and compare book names and the one which is smaller alphabetically will be added to Shelve C till we finish of all the books on both the Shelves

1st comparision 'ab' -> 'ac'            ------>        C = ['ab']

2nd comparision 'bdf' -> 'ac'          ------>        C = ['ab' , 'ac']

3rd comparision 'bdf' -> 'ef'           ------>         C = ['ab', 'ac' , 'bdf']

4th comparision 'bgh' -> 'ef'          ------>         C = ['ab', 'ac', 'bdf', 'bgh']

                                                      ------>          C = ['ab', 'ac' , 'bdf', 'bgh', 'ef']

Now the resulted shelve is also sorted and we did comparision approx (n+m)

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

         first = 0, second = 0;

while(1):

       if(A[first]<B[second]):

                C.insert(A[first])

                first = first +1              # increase value by 1 if book in A is smaller

     

       if(A[first]>=B[second]):

                C.insert(B[second])

                second = second +1   # increase value by 1 if book in B is smaller

For Scenario2:

We can use a very famous technique known as binary search to find the best postion in Shelve A(with "n" books) for each book out of "m" books

Algorithm ArrangingBooksScenario2(A,B,n,m):

         x = B[i]

def insort_right(A, x, lo=0, hi=n): """Insert book x in Shelve A, and keep it sorted. If x is already in A, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """  while lo < hi: mid = (lo+hi)/2 if x < a[mid]: hi = mid else: lo = mid+1 A.insert(lo, x)

Since we are using binary search so the number of comparisions will be "log(n)" for 1 book. Because every time we are dividing the value by 2 so it is like 16->8->4->2->1 so we can find the best location in "log(n)" comparision