Exercises marked with (*) require further reading/search beyond the suggested texts.
1. Find a situation in the improved placement algorithm in which processing a new set in DFS creates no new class.
Answer:
Consider the following sets:
S1 = { 2, 3 }
S2 = { 2, 5, 7 }
S3 = { 3, 5, 7 }
The order S1, S2, S3 is a valid DFS order. When set S3 is added, notice that it does not introduce any new elements, and therefore created no new class.
© 2015 Joao Meidanis