MO640 - Exercises - C1P, Setubal and Meidanis 1997

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.


MO640 Home

© 2015 Joao Meidanis