[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 fi and fj is now
to be defined as
w(i,j) =
min(BM(fi, fj),
BM(fj, fi)),
where BM(fi,fj)
is the minimum number of block-moves to
generate target fj from source fi,
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 fi and fj is now
to be defined as
w(i,j) =
LCS(fi, fj) /
min(|fi|, |fj|),
where LCS is the length of
the longest common subsequence of the contents
of files fi and fj, 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.