1. Questions

computer science(Algorithm)

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.

  1. 👍
  2. 👎
  3. 👁
Traxx

  1. 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?

    1. 👍
    2. 👎
    MathMate

  2. 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?

    1. 👍
    2. 👎
    Traxx

  4. 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.

    1. 👍
    2. 👎
    MathMate

Respond to this Question

First Name

Your Response

Similar Questions

  1. algebra

    Find a formula in terms of k for the entries of A^k, where A is the diagonalizable matrix below. A= 5 -16 2 -7

  2. Augmented Matrix

    Perform row operations on the augmented matrix as far as necessary to determine whether the system is independent, dependent, or inconsistent. DO ALL WORK BY HAND. x + 2y + 4z = 6 y + z = 1 x + 3y + 5z =10 If one subtracts the

  3. Diagonalize

    construct a nondiagonal 2 x 2 matrix that is diagonalizable but not invertible. Just write down a diagonal matrix with one zero on the diagonal and then apply an orthogonal transformation. E.g. if you start with the matrix: A = [1

  4. Algebra

    Given the following vector X, find a non-zero square matrix A such that AX=0: You can resize a matrix (when appropriate) by clicking and dragging the bottom-right corner of the matrix. X= 2 -8 6 A= _ _ _ _ _ _ _ _ _ Please help, I

  1. Matrix

    Let A be an invertible n x n matrix, and let B be an n x p matrix. Explain why (A^-1)(B) can be computed by row reduction: [A B] ~...~ [I X] X=(A^-1)(B)

  2. math

    Find the entries of the following matrices: (a) the 2 ×2 matrix M for the reflection across the line y = x. (b) the 2 ×2 matrix N for the 90 degree counterclockwise rotation about the origin. (c) the product MN;what

  3. Language Arts

    In The Riddle of the Rosetta Stone: Clues to the Puzzle, how does the author best support his claim that Thomas Young was someone who "laid a solid groundwork for others”? A. by providing details about how others reacted to

  4. english

    Please can anyone help me understand how metaphor is being used in the poem, "Tableau".

  1. Math

    Directions: Use the following matrix to perform the elementary row operations sequentially. A=[3 2 |8] [5 2 |12] 1.) (1/3) R1 From the original matrix 2.) -5R1+R R2 From matrix in question 1.

  2. Math

    Given the following matrix A, find an invertible matrix U so that UA is equal to the reduced row-echelon form of A: You can resize a matrix (when appropriate) by clicking and dragging the bottom-right corner of the matrix. A = 3 3

  3. Algebra

    2. Use an augmented matrix to solve the system. x + y = 5 3x – y = –1 (1 point) (1, 4) (1, 5) (3, –1)*** (5, –1) 3. When converting a system of linear equations into an augmented matrix, what equation form is needed? (1

  4. math

    A matrix A is said to be skew symmetric if A^T = -A. Show that is a matrix is skew symmetric then its diagonal entries must all be 0. A^T meant to be A transpose.

You can view more similar questions or ask a new question.