[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.