[CSE2304]
[progress]

### CSSE, Monash University, .au, CSE2304, prac5, 2001

The programs to be written for prac#5
build on [prac#4];
they can be used to find possible "relationships"
between sets of computer programs.

### Group B, starts 21 May 2001

Your employer has decided on a change of plan (like they do):
The weight of the edge between f_{i} and f_{j} is now
to be defined as
w(i,j) =
min(BM(f_{i}, f_{j}),
BM(f_{j}, f_{i})),
where BM(f_{i},f_{j})
is the minimum number of block-moves to
generate target f_{j} from source f_{i},
as covered in [prac#3] (group A).
Remarkably your employer also hired someone else to provide a solution
to prac3(A)
[here] (when the time is right)
and you may use parts of it if you wish.

Modify your program for [prac#4]
so that it uses BM( ), as above,
and calculates and prints a
*minimum*
spanning tree
of the resulting graph.
(Remember a *small* BM value may indicate similar programs.)

[6 marks]

### Group A, starts 28 May 2001

Your employer has decided on a change of plan (like they do):
The weight of the edge between f_{i} and f_{j} is now
to be defined as
w(i,j) =
LCS(f_{i}, f_{j}) /
min(|f_{i}|, |f_{j}|),
where LCS is the length of
the longest common subsequence of the contents
of files f_{i} and f_{j}, as covered in
[prac#3] (group B).
Remarkably your employer also hired someone else to provide a solution
to prac3(B)
[here] (when the time is right)
and you may use parts of it if you wish.

Modify your program for [prac#4]
so that it uses LCS (see above), and calculates and prints a
*maximum* (NB. not minimum)
spanning tree
of the resulting graph.
(Remember a *long* LCS indicates similar programs.)

[6 marks]

© L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3168.