Sunday

April 20, 2014

April 20, 2014

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

(-) 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:20amTo 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:53amINSERT(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:18amObviously 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.

**Related Questions**

Computer Science - Give a modular exponentiation algorithm that examines the ...

Advanced Math - Find DE if matrix D= Row 1= -2,4,6 and ROW 2= 5,-7,1 and matrix ...

algebra - When i have a matrix 4 X 4 and i have to multiply it by a 4 X 3 i know...

Algebra II-Please check calcs - Could someone check this matrix calculation The ...

math - what do we call numbers that cannot be arranged into 2-row arrays? A ...

Math - A message was encoded using the matrix [7 2 3 1] and you can decode the ...

math help - Can someone explain to me the following step by step , i 've looked ...

Matrix - How do you solve for this matrix. X*X^t=0? What matrix times its ...

linear algebra - 1)If A is an invertible matrix and k is a positive integer, ...

Augmented Matrix - Perform row operations on the augmented matrix as far as ...