2
\$\begingroup\$

The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain (1..n) under the operation INSERT and EXTRACT-MIN. We are give a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in (1,2..n) is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call".

For example: if S is ["5","4","6","E","1","7","E","E","3","2"] (E stands for EXTRACT-MINS) then your program should return 4,1,5.

Here is the tip given in the textbook Introduction to algorithms:

We break the sequence into homogeneous subsequences:

I1, E, I2, E, I3..... Im, E, I(m+1)

where each E represents a single EXTRACT-MIN call and each I(j) represents a (possibly empty) sequence of INSERT calls. For each subsequenc I(j) we initially place the keys inserted by these operations into a set K(j) which is empty if I(j) is empty. Then do the following:

OFF-LINE-MINIMUM(m,n)
for i= 1 to n
       determine j such that i is part of K(j)
       if (j != m+1)
           extracted[j]= i;
           let l be the smallest value greater than j
                for which set K(l) exists
           K(l) = K(l) + K(j) (unite the 2 sets), destroying K(j)
return extracted

My code implements the disjoint-sets data structure with union-by-rank and path compression heuristic. You can look them up here.

include <stdio.h>   //Problem: Off-line minimum
#include <conio.h>

#define MAX 100
#define YES 1
#define NO 0
#define INVALID -1

int input(int *N, int *M, int *list);

int Offline(int N, int M, int *list, int *extract);

int make_disjoint(int x, int *parent, int *rank);

int union_disjoint(int x, int y, int *parent, int *rank);

int link_disjoint(int x, int y, int *parent, int *rank);

int find_disjoint(int x, int *parent, int *rank);

int main()
{
 int N=9 ,M=6;
 int list[MAX]={3,7,-1,2,-1,8,1,5,-1,-1,-1,0,6,-1,4};
 int extract[MAX]={-1},i;
 for (i=0; i<MAX; i++)
    extract[i]=-1;
 Offline(N,M,list,extract);
 getch();
 return 0;
}

int input(int *N, int *M, int *list)
{
 FILE *f;
 int i;
 f=fopen("OFFLINE.txt","r");
 fscanf(f,"%d %d",N,M);
 for (i=0; i< (M+N); i++)
    fscanf(f,"%d",&list[i]);
 fclose(f);
 return 0;
}

int make_disjoint(int x, int *parent, int *rank)
{
 parent[x]=x;
 rank[x]=0;
 return 0;
}

int union_disjoint(int x, int y, int *parent, int *rank)
{
 link_disjoint(find_disjoint(x,parent,rank), find_disjoint(y,parent,rank),parent,rank );
 return 0;
}

int link_disjoint(int x, int y, int *parent, int *rank)
{
 int rootx, rooty;
 if (y==INVALID)
    return 0;
 rootx= find_disjoint(x,parent,rank);
 rooty= find_disjoint(y,parent,rank);
 parent[rootx]=parent[rooty];
 if (rank[rootx]== rank[rooty])
    rank[rooty]++;
 return 0;
}


int find_disjoint(int x, int *parent, int *rank)
{                                                //Path compression heuristic
 if (parent[x]!=x)
    x = find_disjoint(parent[x], parent, rank);
 return x;
}



int Offline(int N, int M, int *list, int *extract)
{
 int position,dem,i,j,rank[MAX]={0},parent[MAX],pos[MAX];
 int dump[MAX]={-1},cdump;
 int count,exist[MAX]={YES},q,l;
 int list1[MAX],extract1[MAX];
 int root[MAX];
 for (i=0; i<MAX; i++)
 {
    list1[i]= list[i];
    pos[i]=INVALID;
    extract1[i]=extract[i];
    exist[i]=INVALID;
    root[i]=INVALID;
    parent[i]=INVALID;
 }
 position=0;
 cdump=-1;
 for (dem=1; dem <= M+N ; dem++)
 {
    if (list[dem-1]==INVALID)
    {
        position++;
        if (cdump> -1)
        {
            exist[position-1]=YES;
            make_disjoint(dump[0],parent,rank);
            for (i=1; i<=cdump; i++)
            {
                make_disjoint(dump[i],parent,rank);
                union_disjoint(dump[i], dump[0],parent,rank);
                //root[position-1]= find_disjoint(dump[0],parent,rank);
            }
            root[position-1]= find_disjoint(dump[0],parent,rank);
            cdump = -1;
        }
    }
    else
    {
        pos[ list[dem-1] ] =position;
        cdump++;
        dump[cdump] = list[dem-1];
    }
 }
 if (cdump> -1)
 {
    make_disjoint(dump[0],parent,rank);
    for (i=1; i<=cdump; i++)
    {
        make_disjoint(dump[i],parent,rank);
        union_disjoint(dump[i], dump[0],parent,rank);
        //root[position-1]= find_disjoint(dump[0],parent,rank);
    }
    exist[position]=YES;
    root[position]= find_disjoint(dump[0],parent,rank);
    cdump = -1;
 }

 count = M;
 for (i=0; i<N; i++)
 {
    j= pos[ find_disjoint(i,parent,rank)  ];
    if (j!= M)
    {
        extract[j]= i;
        extract1[j]=i;
        q=NO;
        for (l=j+1; l<=M; l++)
        {
            if ((exist[l]==YES)||(exist[l]==INVALID))
            {
                q=YES;
                break;
            }
        }
        if (q==YES)
        {
            union_disjoint(root[j],root[l],parent,rank);
            if (root[l]==INVALID)
            {
                exist[l]=YES;
                root[l]=root[j];
                pos[root[l]]=l;
            }
            else
            {
                pos[root[l]]=l;
            }
            exist[j]=NO;
            q++;
        }
    }
 }
 return 0;
}

I took too much time to finish it, so I figured that something must be wrong. For example, looking at the function Offline, you can see how complex and entangled it is. The code doesn't seem to follow the pseudocode anymore. Please help me how to improve the code and give me detailed reviews.

\$\endgroup\$
2
\$\begingroup\$

Your code needs some better formatting to be readable. Right now everything is a jumbled mess. These suggestions will improve the readability of your code (in no particular order).

  1. One variable declaration per line. Which do you think is easier to read?

    int position,dem,i,j,rank[MAX]={0},parent[MAX],pos[MAX];
    
    int position;
    int dem;
    int i;
    int j;
    int rank[MAX] = {0};
    int parent[MAX];
    int pos[MAX];
    
  2. Indent the lowest indentation level in functions by the same amount as other lines.

    int union_disjoint(int x, int y, int *parent, int *rank)
    {
        link_disjoint(find_disjoint(x,parent,rank), find_disjoint(y,parent,rank),parent,rank );
        return 0;
    }
    
  3. Insert spaces around operators and after commas.

    if (cdump > -1)
    {
        exist[position - 1] = YES;
        make_disjoint(dump[0], parent, rank);
        for (i = 1; i <= cdump; i++)
        {
    
  4. Use descriptive variable names. It's hard to tell what N, M, q and l are when reading the code.

  5. Try to keep functions short. Let them do just one thing each. The Offline function is really long, maybe you can split it into a at least two smaller ones.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.