070-2015

MO640 - Multiple-choice question

To test for the C1P on a connected component of the strict overlap graph, we need to keep a linear order (called Path in the figure below) of twin classes, and update the structure with each new set added.

Suppose that a certain number of sets have been processed, with the C1P being satisfied so far, and  arriving at the structure shown below.



When adding a new set S, the current classes can be classified into three categories:

•  empty (no elements in common with S),
•  full (contained in S), or
•  partial (some, but not all, ements contained in S).

 Adding set S = {3, 4, 8, 9} to this data structure: 

1. ... the C1P would be destroyed because there is a twin class of new elements but not a suitable extremity in the path to place it.
2. ... the C1P would still hold true.
3. ... the C1P would be destroyed because some class is partial and there is no empty neighbour or free extremity to place the subclass disjoint from S.
4. ... the C1P would be destroyed because the updated classes contained in S do not form a consecutive block.
5. None of the above.

Original idea by: Celso A. W. Santos

069-2015

MO640 - Multiple-choice question

When testing for the C1P on a connected component of the strict overlap graph, one startegy is to keep a linear order of twin classes for the sets already processed, and update this structure for each new set added.

Suppose a correct twin-class path for an already processed subfamily that has the C1P is as follows:

 

 Which of the following sets would violate the consecutive ones property if added?

1. {1, 3, 6, 7}
2. {2, 7}
3. {3, 4, 6}
4. {4, 5, 7, 8}
5. None of the above.

Original idea by: Juan Felipe Hernández Albarracín

068-2015

MO640 - Multiple-choice question

Call T(U) the collection of the trivial subsets of U.
The complete collection of C = {bfg, cdef, abcd} under U = abcdefg is:

a) T(U) ∪ {ab, abcd, abcdef, abcdfg, acd, bcdefg, bfg, bg, cd, cde, cdef, ef, fg}
b) T(U) ∪ {ab, abcdef, abcdfg, bcdefg, bdfg, bg, cd, cde, cdef, ef, efg, fg}
c) T(U) ∪ {abcd, abcdef, abcdfg, acd, bcdfeg, bfg, cde, cdef}
d) T(U) ∪ {abcdef, abcdfg, bcdfeg}
e) None of the above

Original idea by: Miriam Ito

077-2007

MO640 - Multiple-choice question

Considering the PQR tree below, which of the alternatives contains sets that do NOT belong to the tree's complete collection?

a) { M N } and { M O }
b) { C D } and{ K L }
c) { A B }, { J K }, and { L M }
d) { E F G }, { G H }, and { H I }
e) None of the above.

Original idea by: Daniel M. Ivasse
Translation help by: Mario Akita

067-2015

MO640 - Multiple-choice question

To test for the C1P on a connected component of the strict  overlap graph, we need to keep a linear order of twin classes for the sets already processed, and update this structure as each new set is added.

Suppose we are processing the following sets in the order they are given below:

S1 = {1,4}
S2 = {1,3,5}
S3 = {3,2,5}
S4 = {1,3,2}

Mark the CORRECT option describing what happens when set S4 is added.

a) The C1P is destroyed because there is no suitable location to place the class {5} that was split from an existing class.
b) The C1P is destroyed because there is no suitable location to place the class {2} that was split from an existing class.
c) The C1P is destroyed because there is no suitable location to place the class {3} that was split from an existing class.
d) The C1P is destroyed because not all updated classes contained in S4 can be kept consecutive.
e) None of the above.

Original idea by: Raphael Cristofaro 

076-2007

MO640 - Multiple-choice question

Choose the WRONG alternative regarding PQ-Tree and PQR-Tree:

1. Every PQ-Tree is a PQR-Tree, but the reverse is not true.
2. The children of an R node can be freely permuted in equivalente transformations, and the same holds for Q nodes.
3. Intersection, disjoint union and noncontained complement are operations that can be used to calculate the completion of a set family.
4. There is always a PQR-Tree that represents a finite family of restrictions over a finite universe.
5. None of the Above.

Original idea by: Celmar Guimarães da Silva
Translation help by: Andrey Victor Justo

114-2008

MO640 - Multiple-choice question

Let C = { abcd, bcdef, afghijk, bcdgh, ghijk }. Choose the alternative that contains all nontricial sets of twins from C:

1) abc, gh, ijk
2) bcd, ef, hij
3) bcd, gh, ghi
4) bcd, gh, ijk
5) None of the above

Author: Victor de Abreu Iizuka
Translation help by: Rafael S. Padilha