# computer science(Algorithm)

posted by .

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) -

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) -

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) -

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.

## Similar Questions

1. ### math , help

can someone show me how to solve this: directions: pivot once as indicated in each simplex tableau. Read the solution from the result. the number that is highlighted is row 2 column 3 which is the 5 the matrix is a 4 X 8 under column …
2. ### algebra

When i have a matrix 4 X 4 and i have to multiply it by a 4 X 3 i know that the product size has to be a 4x 3 so do i do a row times column or how ?
3. ### college math

13. (4 pts) At an annual flower show, 6 different entries are to be arranged in a row. a) How many different arrangements of the entries are possible?
4. ### Algebra II-Please check calcs

Could someone check this matrix calculation The first matrix dimension is 1 by 3 row 1 = 1 row 2 = 7 row 3 =3 Second matrix is 1 by 3 Row 1 column one =2 row 1 column two = -5 row one column three = 5 my calculation is that it would …
5. ### Simple Array Process

need help with this generate only the pseudocode. No charting is required, but you will have to incorporate the bubble sort algorithm to ensure the selling prices are in order so you can determine the median selling price. Do not assume …
6. ### computer science

Python 3 For this option, you will first ask "how many rows?
7. ### Java programming

can anybody help me.. Multidimensional Array Use a two-dimensional array (for example of 3 by 3) to simulate the addition operation of two matrices. Sample output: the first matrix: 1 2 3 1 0 1 1 2 1 the second matrix: 1 1 1 2 2 2 …
8. ### programming-datastructures

Compute a new sorted list that represents the intersection of the two given sorted lists....
9. ### Precalculus

Find the values of x and y. Matrices.. [-4 2 3 5 3 5 2 -3 1] TIMES [2 x 5] EQUALS [9 38 y] It is difficult for me to type the matrices in but.... The first matrix is 3x3 consisting of -4,2,3 in the first row.. 5,3,5 in the second row …
10. ### linear(hw check)

determine if v1= [ 2 1 0] v2=[ -1 1 3] v3=[ 0 -1 6] spans the vector space of rows with three real entries which has dimension 3. so I wanted to make sure I did this correct. First I created a matrix with v1,v2,v3 as the columns (so …

More Similar Questions