Young’s Table

A Young’s table is a mxn matrix such that the entries of each row are in sorted order from left to right and the entries in each column are in sorted order from top to bottom. Some of the elements in the matrix can have the value infinity, which are actually non existing elements. The total number of elements is therefore less than or equal to mxn. And there can me be more than one representations of a Young’s table for a given set of elements.The algorithms for all the Young’s Table operations are:
1.This operation sees to it that the Young’s Table condition is satisfied for a part of the matrix starting from index i,j and having size ixj.YOUNGIFY(A,x,y):
small=A(x,y)

if y+1<=A.maxcolumn and A(x,y+1)<small
small=A(x,y+1)
p=x and q=y+1

if x+1<=A.maxrow and A(x+1,y)<small
small=A(x+1,y)
p=x+1 and q=y

if small!=A(x,y)
swap values of A(x,y) and A(p,q)
YOUNGIFY(A,p,q)2.This is a operation to build the Young’s Table.BUILD(A):
for i in range(A.maxrow,1)
for(j in range(A.maxcol,1)
YOUNGIFY(A,i,j)3.This is the operation to extract the minimum element from the Young’s table.EXTRACT-MIN(A):
min=A(1,1)
swap A(1,1) and A(A.maxrow,A.maxcol)
A.size=A.size-1
YOUNGIFY(A,1,1)4.This is the operation to increase the value of an element at a particular index.INCR(A,p,q):
large=A(p,q)

if p-1>=1 and p-1large
large=A(p-1,q)
x=p-1
y=q

if q-1>=1 and q-1large
large=A(p,q-1)
x=p
y=q-1

if large!=A(p,q)
swap A(p,q) and A(x,y)
INCR(A,x,y)5.This is a operation to insert an element.INSERT(A,key):
if A is full
print ‘Error’
return
A.size+=1
A[A.maxrow][A.maxcolumn]=key
incr(A,A.maxrow,A.maxcolumn)The running time of YOUNGIFY is O(m+n). And the running time of BUILD is n2 times O(m+n). Here m is A.maxrow and n is A.maxcolumn. All other operations take O(m+n) time. The C code for Young’s table is:#include<stdio.h>
int m,n,num;

void youngify(int** a,int x,int y)
{
int small,p,q,temp;
small=a[x][y];
p=x;
q=y;

if((y+1)<n && a[x][y+1]<small)
{
small=a[x][y+1];
p=x;
q=y+1;
}

if((x+1)<m && a[x+1][y]<small)
{
small=a[x+1][y];
p=x+1;
q=y;
}

if(p!=x || q!=y)
{
temp=a[x][y];
a[x][y]=a[p][q];
a[p][q]=temp;
youngify(a,p,q);
}

}

void build(int** a)
{
int p,q,i,j;

for(i=m-1;i>=0;i–)
{
for(j=n-1;j>=0;j–)
{ youngify(a,i,j);
}
}

}

int extract_min(int** a)
{
int ret;

ret=a[0][0];
a[0][0]=a[m-1][n-1];
num=num-1;
youngify(a,0,0);
return ret;
}

void display(int** a)
{
int i,j;
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{
printf(“%d “,a[i][j]);
}
printf(“n”);
}
}

void incr(int** a,int p,int q)
{
int large=a[p][q],i,j,temp;

if((p-1)>=0 && (p-1)<m && a[p-1][q]>large)
{ large=a[p-1][q];
i=p-1;
j=q;
}
if((q-1)>=0 && (q-1)<n && a[p][q-1]>large)
{
large=a[p][q-1];
i=p;
j=q-1;
}

if(large!=a[p][q])
{
temp=a[p][q];
a[p][q]=a[i][j];
a[i][j]=temp;
incr(a,i,j);
}
}

void insert(int** a,int key)
{
if(num>=m*n)
{
printf(“nTable full!!!”);
return;
}
num=num+1;

a[m-1][n-1]=key;
incr(a,m-1,n-1);
}

int main()
{
int i,j,k,arr[20];
int** a;
k=0;

printf(“Give the number of elements(max 20 and less than 999):”);
scanf(“%d”,&num);

printf(“nSize of matrix:nRows:”);
scanf(“%d”,&m);
printf(“nColumns:”);
scanf(“%d”,&n);

printf(“nGive the elements: “);
for(i=0;i<num;i++)
scanf(“%d”,&arr[i]);

a=(int**)malloc(m*(sizeof(int*)));
for(i=0;i<m;i++)
a[i]=(int*)malloc(n*sizeof(int));

for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{ if(k<num)
{
a[i][j]=arr[k];
k+=1;
}
else
a[i][j]=999;
}
}
printf(“n”);

printf(“nThe initial Young’s table is:n”);
build(a);
display(a);

extract_min(a);
printf(“nAfter extracting minimum element:n”);
display(a);

insert(a,1);
printf(“nAfter inserting the element ‘1’:n”);
display(a);

free(a);

return 0;
}Some of the changes in this code are that infinity is considered to be 999 and also the matrix starts from (0,0) unlike the algorithms where it starts from (1,1).

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *