Posted by **Traxx** on Thursday, October 21, 2010 at 9:05am.

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.

- computer science(Algorithm) -
**MathMate**, Thursday, October 21, 2010 at 9:20am
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?

- computer science(Algorithm) -
**Traxx**, Thursday, October 21, 2010 at 9:53am
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?

- computer science(Algorithm) -
**MathMate**, Thursday, October 21, 2010 at 10:18am
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.

## Answer This Question

## Related Questions

- Algebra II-Please check calcs - Could someone check this matrix calculation The ...
- algebra - When i have a matrix 4 X 4 and i have to multiply it by a 4 X 3 i know...
- math , help - can someone show me how to solve this: directions: pivot once as ...
- Precalculus - Find the values of x and y. Matrices.. [-4 2 3 5 3 5 2 -3 1] TIMES...
- linear(hw check) - determine if v1= [ 2 1 0] v2=[ -1 1 3] v3=[ 0 -1 6] spans the...
- college math - 13. (4 pts) At an annual flower show, 6 different entries are to ...
- Java programming - can anybody help me.. Multidimensional Array Use a two-...
- computer science - Python 3 For this option, you will first ask "how many rows...
- math - If A^TA is an invertible matrix, prove that the column vectors of A are ...
- Math - At an annual flower show, 6 different entries are to be arranged in a row...

More Related Questions