MO640 - Exercises - C1P, Setubal and Meidanis 1997

Exercises marked with (*) require further reading/search beyond the suggested texts.

4. Find a situation in the improved placement algorithm in which processing a new set in DFS destroys the C1P by not having all full classes consecutive.

Answer:

Consider the following sets:

S1 = { 3, 2 }
S2 = { 2, 5, 7 }
S3 = { 5, 7, 6 }
S4 = { 3, 5, 6 }

The Strictly Overlapping Graph for Sets S1, S2, S3 and S4 is:

Strictly Overlapping Graph

These sets are inserted in the data structure in the following DFS order: S1, S2, S3, S4. The data structure after inserting S3 would be:

path of twin classes, before

So far, the C1P holds true. However, once we insert S4 by following the improved placement algorithm, we would colour the elements of S4 (3, 5 and 7) as follows:

path of twin classes, after

According to line 8 of the algorithm (if nonconsecutive full classes: C1P <- false), the C1P is now destroyed thanks to S4, because not all full classes are consecutive.


MO640 Home

© 2015 Joao Meidanis