Question

In an attempt to explain what an elder matrix is: it is a n by m matrix in which each row and each column is sorted in ascending order.

Inputs in the matrix can either be finite integers or ∞. the ∞symbol is used when accounting for nonexistent inputs.

for all questions below please answer using pseudocode and explainations

(a) create an algorithm EXTRACT-MIN on an Elder Matrix that is not empty. the algorithm must run in O(m+n) time. The algorithm must use a recursive function that solves an m by n problem by recursively solving a (m-1) by n problem or a m by (n-1) problem.

(b)create an algorithm INSERT of an integer into a m by n Elder Matrix that runs in O(m+n) time.

(c) Using no other sorting method as a subroutine, show how to use a n by n Elder Matrix to sort n2 numbers in O(n3) time. (Suppose we let k = n2. Then this is an O(k1.5) sorting algorihm

Answer 1

//An 2D-array that will contain all the elements, initially all the elements will be infinite

//"inf" shows the infinite value

Elder_matrix = ("inf") for range(n,m)

Ans a)

We know the elements are arranged in the ascending sorted order for each row and column, so for sure we'll get the minimum element at [0][0] of the matrix and then we would require to rearrange the elements.

After taking minimum value from the [0][0] position we'll insert "inf" value at that place. Then after we'll go down (move down i.e. move along column) if value of down<right else we'll go right (move right i.e. move along row) until we won't reach the end of the Elder matrix.

(You'll understand the concept once you'll go by the code and will try to solve with a small example)

Eg:

Let Elder matrix is

1 4 6

3 5 7

5 6 9

We extracted min i.e. 1 and inserted "inf"

Now Elder matrix is

"inf" 4 6

3 5 7

5 6 9

Now down = 3 and right = 4, clearly down<right, So swap 3 to "inf", as

3 4 6

"inf"   5 7

5 6 9

Now we are at (1,0) and down = 5 and right = 5, clearly down = right, So swap 5 to "inf"

3 4 6

5 "inf" 7

5 6 9

Now we are at (1,1) and down = 6 and right = 7, clearly down<right, so swap 6 to "inf"

3 4 6

5 6    7

5 "inf" 9

Now we are at (2,1) and right = 9 and down = "inf"(we'll take "inf" if we are at last row), So, right<down and thus

swap 9 with "inf"

3 4 6

5 6    7

5 9 "inf"

Now, we are at (2,2) and down = right so we'll end. See we have extracted the min element and still the Elder matrix is sorted row and column wise both.

Algorithm

//Actual function to be called for the extract min from Elder_matrix

function extract_min(Elder_matrix){

if (Elder_matrix[0][0] == "inf")

return

else{

min = Elder_matrix[0][0]

  Elder_matrix[0][0] = "inf"

arrange(Elder_matrix)

return min

}

}

//Function that must not be called by the user

function arrange(Elder_matrix, i=0, j=0){

//Values of below and right where be currently are

down = "inf"

right = "inf"

if (i+1 < n)

down = Elder_matrix[i+1][j]

if (j+1 < m)

right = Elder_matrix[i][j+1]

//End case

if (down == "inf" and right =="inf")

return

//Go down if down<right

if (down<right){

//swap Elder_matrix[i][j] with Elder_matrix[i+1][j]

swap(Elder_matrix[i][j], Elder_matrix[i+1][j])

arrange(Elder_matrix, i+1, j)

}

  //Go right if down>=right

if (down>=right){

//swap Elder_matrix[i][j] with Elder_matrix[i][j+1]

swap(Elder_matrix[i][j], Elder_matrix[i][j+1])

arrange(Elder_matrix, i, j+1)

}

}

Ans b)

So, insert is very easy. We'll insert the element at bottom right corner of the Elder matrix and will move upward till we encounter a value less than inserted value. Then after we'll move that value to the left until it reach to the column 1 or encounter a value less than that. This is a very simple logic.

Algorithm

//Actual function to be called for the insertion of an element in Elder_matrix

function insert_elder_matrix(Elder_matrix, value){

if (Elder_matrix[n-1][m-1] < "inf"{

print("Elder matrix is full.")

return

}

else{

  Elder_matrix[n-1][m-1] = value;

insert_elder_matrix_2(Elder_matrix, n-1,m-1)

}

}

//Function that must not be called by the user

function insert_elder_matrix_2(Elder_matrix, i, j){

if (i==0 and j==0)

return

if (i>0){

if (Elder_matrix[i][j] < A[i-1][j]){

swap(Elder_matrix[i][j], Elder_matrix[i-1][j]

  insert_elder_matrix_2(Elder_matrix, i-1, j)

}

  if (i>0){

if (Elder_matrix[i][j] < A[i][j-1]){

swap(Elder_matrix[i][j], Elder_matrix[i][j-1]

  insert_elder_matrix_2(Elder_matrix, i, j-1)

}

}

}

Note: function swap(x,y) will swap the values of x and y

Ans c)

First of all we will take an empty array/list. Then one by one we will extract minimum element from the Elder matrix and will store that element into that list sequentially. When no element will be left in the Elder matrix, we'll get the list of sorted n^2 elements.

Time Complexity:

When we are given n^2 elements that means n=m

For extracting minimum element = O(n+m) = O(2n) = O(n)

Also we'll extract minimum element for n^2 times, because there are n^2 elements and we are extracting minimum element each time for each element. So,

T(n) = n^2 * O(n) = O(n^3)

Time Complexity = No. of iteration * Time complexity of extract_min function

Hence for finding sorted list of n^2 elements above approach's time complexity is O(n^3).