An m X n YOUNG TABLEAU is an m X n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of YOUNG TABLEAU maybe ¡Þ, which we treat as nonexistent elements, Thus, a YOUNG TABLEAU can be used to hold r¡Ü m n finite numbers.
(-) show how to insert a new elements into non-full m X n YOUNG TABLEAU in
O(mXn)time.
To make sure we are on the same wavelength, to me it is implicit that
1. the matrix entries are numeric
2. the insertion will preserve the given order horizontally and vertically,
3. location of non existent elements are unpredictable, and
4. The insertion of an element in a row involves shifting of elements, which in turn will disrupt the order of the elements in the columns. This has to be addressed (in mxn time!)
Do you have any suggestions?
INSERT(Y; k)
DECREASE-KEY(Y; m; n; k)
DECREASE-KEY(Y; i; j; k)
if Y [i; j] · k
then return error
Y [i; j]Ãk
thresholdÃ1
largestiÃi
largestjÃj
while(i > 1 or j > 1) and Y [i; j] < threshold
do exchangeY [i; j] $ Y [largesti; largestj ]
iÃlargesti
jÃlargestj
if i ¡ 1 ¸ 1 and Y [i; j] < Y [i ¡ 1; j]
then largestiÃi ¡ 1
largestjÃj
if j ¡ 1 ¸ 1 and Y [largesti; largestj ] < Y [i; j ¡ 1]
then largestiÃi
largestjÃj ¡ 1
thresholdÃY [largesti; largestj ]
Is this method help?
Obviously in your algorithm, some of the > and ≥ signs have not been coded properly for HTML.
This is a one-pass algorithm that does the work in O(m+n) BUT it does not guarantee the integrity of the tableau, namely after any exchange, there is no guarantee that both elements satisfy the criteria in both directions (see #4 above).
If that's what your teacher accepts, that's OK.
Example:
1 3 4 X
4 5 9 X
X X X 2
1 3 4 X
4 5 9 2
X X X X
1 3 4 X
4 5 2 9
X X X X
1 3 2 X
4 5 4 9
X X X X
1 2 3 X
4 5 4 9
X X X X
Note that row two violates the Young Tableau criteria.
To insert a new element into a non-full m x n Young Tableau in O(m x n) time, you can follow the steps below:
1. Start at the top-right corner of the Young Tableau (i.e., row 1, column n).
2. Compare the new element with the current element in that cell.
- If the new element is smaller, move one cell to the left (decrementing the column number).
- If the new element is larger, move one cell downwards (incrementing the row number).
- If the new element is equal to the current element or larger than any element below it, stop the process.
3. Repeat step 2 until you find a suitable position for the new element or reach the bottom-left corner of the Young Tableau (i.e., row m, column 1).
4. Insert the new element at the found position.
5. If the insertion causes the row or column to be sorted out of order, perform the appropriate swaps to restore the sorted order.
- To maintain row-wise sorting, swap the new element with the element to its left until it is in the correct position.
- To maintain column-wise sorting, swap the new element with the element above it until it is in the correct position.
6. Repeat steps 2-5 until all elements are inserted into the Young Tableau.
The time complexity of this algorithm is O(m x n) because we may have to iterate through all cells of the m x n Young Tableau to find the suitable position for the new element.