Hints on Project 2

Uppbygging tölva, fall 2001

In the project you are to implement the Quick-find method for the Union-Find problem. It uses the vector id. At each time the following will hold:

If id[p] = id[q] then the elements p and q are in the same set.

The Find operation will then be very fast, because you only have to compare the value of two items in the array id. The Union operation is is much more expensive, as you have to go through the entire array and update values.

Each item of the array id is two bytes. This means that we have to double the values of indices before they are added to the basepointer of the array. Initially we have that DS:SI points to id[0] and assume that BX is the index p in the program. To get id[p] we first have to double BX, e.g. with a shift operation, add it to SI and then divide BX by 2 to get the original value of p. Below is a piece of code that does this:

              ...
           shl     bx, 1             ; Double BX to index a word-array
           mov     ax, [si+bx]       ; Get A[p]
           shr     bx, 1             ; Change BX back to p
              ...
Note that the QF-function is to be independent, without any global variable. There are to be no declared variables in the data segement for the QF-function. Of course you need to declare space fro the array id, but it is declared in the main program and a pointer to it sent down to the function. If you need to use extra memory in the function use the stack (with push and pop), but you should be able to make do with only the registers. You can use the registers AX, BX, CX (a parameter), DX (a parameter), DI, SI (a parameter) and BP (note that if BP is used as a pointer you need to put DS: in front of it). Remember to save the registers that you change at the start of the function and the recover them at the end of the function.

Here is a better random number generator: slembi16.asm, for the one that care for such things. This function is a bit slower and uses both AX and DX for initial value (seed).


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