1
$\begingroup$

This are two sections from a task I got.

The Young tableau is defined as a matrix of m rows on n columns so that the bars in each row are sorted in ascending order Left to right and the elements in each column are sorted in ascending order from top to bottom. Some of the elements in the Young tableau may be $\infty$ we will refer to these elements as non-existent elements . Therefore, the Young tableau can be used to hold finite numbers.

  1. Write an algorithm for EXTRACT-MIN on a non-empty Young tableau of m at n in time running $O(n+m)$
  2. Show how to insert a new element into a non-complete Young tableau v at the size of m at n in time running $O(m+n)$

That's what I tried:

When I remove the element at the $(1,1)$ I need to move every element in the table 1 step left (and if the col is 1 so move one row up and put it on the last col) so I can solve it on $O(n*m)$. I think that $O(m+n)$ actually measn $O(max(m,n))$

Regarding the second clause I was thinking to compare the element to insert with the element in the first col in every row until until we get to bigger one and then and then check on this row where to insert it. But again let's say that I want to insert element which will be the min on the new table, so I need to push all the elements one stop left and it takes $O(m*n)$

$\endgroup$
4
  • $\begingroup$ Can you clarify what do you mean by insert a single element? Inserting a row or a column is clear but how is a single element inserted? I would insert a single row and column just at the cell where the new element should be placed. And assign all values with inf. If you store your table as a grid of linked list then it takes m + n operation. But I am not sure what you mean. $\endgroup$
    – fade2black
    Jun 13 '17 at 18:06
  • $\begingroup$ The table is 2D array. Let's say that the elements are numbers and I want to insert a number. $\endgroup$
    – omer adam
    Jun 13 '17 at 18:52
  • $\begingroup$ Have a look here. It may help you. It says that complexity of insertion is O(max(n,m)). In fact max(n,m) is O(n+m), so there's nothing wrong with it if you say that it is O(n+m). $\endgroup$
    – fade2black
    Jun 13 '17 at 20:12
  • $\begingroup$ Jeu de taquin might be relevant here. $\endgroup$ Jun 14 '17 at 6:56
3
$\begingroup$

Hint: For EXTRACT-MIN, instead of thinking in terms of shifting rows/columns, try to replace the element at $(1,1)$ by $+\infty$. Now you just want to swap $+\infty$ with one of his neighbour until you get the invariant of a Young tableau. How can you decide where to move it?

$\endgroup$
1
$\begingroup$

Here you can take reference from this link, where above stated algo to find the minimum is explained in a simple way: https://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/

And for Young Tabeleu method, you can refer this link: http://mathworld.wolfram.com/YoungTableau.html

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to the site! Those links probably do answer the question but we're really looking for actual answers, rather than pointers to answers elsewhere. It would be helpful if you could write a dew sentences summarizing the content of those links so that your answer will still contain useful information if (when!) the links stop working. $\endgroup$ Feb 25 '18 at 13:24
-1
$\begingroup$

I am agreeing with the hint provided by @md5, you simply swap the max element with (1, 1) and then swap that max element with the minimum value present in either next column or next row. This way the total number of element you compare or traverse will be ( m + n) which I think will be maximum. For the second clause you first insert the value in empty field in the matrix and then again start traversing but in backward direction and try to replace you newly inserted value with maximum value found in either in current column or previous column. Again you will end up traversing ( m + n) elements. And be sure to check for boundary cases which can save few running time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.