08.71.35 Uppbygging tölva

Programming project 2


In this project you are to write a function in 16-bit x86 assembly language that implements the Quick-find solution of the Union-Find problem that you should recognize from Tölvunarfręši 2.

The function that you are to write gets in DS:SI a pointer to the vector id, which is an uninitialized N-item vector of 16-bit words, in CX is the value N, which is the number of items in id and in DX is the value M, which is the number of unions that are to be performed. The function initializes the vector id and then updates it according to random unions. The random numbers are from the function slembi, which returns a 16-bit random number that you have to scale, such that it is between 0 and N-1.

Below is a C++ version of Quick-find.

	void QuickFind( int id[], int N, int M )
	{
	    int i, j, p, q;
	
	    for( i=0; i<N; i++ )
	        id[i] = i;
	
	    for( j=0; j<M; j++ ) {
	        p = slmb(N);  q = slmb(N);
	        int t = id[p];
	        if (t == id[q]) continue;
	        for( i=0; i<N; i++ )
	            if (id[i] == t) id[i] = id[q];
	    }
	}
In the program we assume that the function slmb(N) returns a random number between 0 and N-1.

You are also to write a main program that defines a 10000 item vector and calls QuickFind with N=10000 and M=10000. Then the program could use the resulting vector id to do some Find-operations. However, you don't have to write that part.

If you don't want to always start with the same initial value in the random number generator, then you can utilize the fact that DOS stores a 32-bit counter in 0040:006C, that is incremented 18.2 time a second.


Return a printout by thursday october 18th.

hh (hja) hi.is, october 10th, 2001.