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:
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:
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:
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.
© 2015 Joao Meidanis