Week 15 - Consecutive ones property

Consider the sets being processed by the improved placement algorithm (DFS corresponds to the order they are given):

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

Now mark the CORRECT option that describes what happens when set S4 is added.

a) The C1P is destroyed because there is no empty neighbor to place the element {5} that was split from its class.
b) The C1P is destroyed because there is no empty neighbor to place the element {2} that was split from its class.
c) The C1P is destroyed because there is no empty neighbor to place the element {3} that was split from its class.
d) The C1P is destroyed because not all full classes are consecutive.
e) None of the above.

Original idea by: Raphael Cristofaro 

Week 14 - PQ-trees

Which of the bellow statements is INCORRECT?

a) Reading the leaves of a tree T from left to right yields its frontier, denoted by
FRONTIER(T).
b) A null tree (which has no nodes) is NOT considered as a PQ-tree.
c) A reversal of a P node is a equivalence transformation.
d) A reversal of a Q node is a equivalence transformation.
e) None of the above.

Translated by: Raphael Cristofaro
Original idea by: Moacy Barros Correia da Silva
(question number 071)

Week 13 - Dictionary order

As described by Benzer (1959), for n mutants, the probability that a randomly chosen, symmetric, binary matrix can be arranged in dictionary order is n!/2^{n(n- 1)/2}. Consider the following statements about the above expression and mark the INCORRECT one:

a) The number 2 raised by the expression n(n- 1)/2 relates to the matrix data alphabet (zeros and ones).
b) The number 2 raised by the expression n(n- 1)/2 relates to the matrix dimensions (columns and rows).
c) n! is the number of rearrangements that any given set of data may be subjected in one specific dimension (columns or rows).
d) n! is the number of possible row arrangements in satisfactory patterns.
e) None of the above.

Original idea by: Raphael Cristofaro

Week 12 - Unichromosomal genomes: block interchange

Select the alternative with the minimum number of block interchange operations that are needed to sort optimally the following genome:

+1 +8 +4 +7 +5 +2 +9 +6 +3 +10

a. 2.
b. 3.
c. 4.
d. 5.
e. None of the above.

Week 11 - Unichromossomal genomes, reversal

Given the permutation (0 2 4 3 5 1 6 8 7 9), consider the following statements according to the definitions by Bergeron (2005) on the Hannenhalli-Pevzner Theory.

I - This permutation contains only a simple hurdle, which is 2 4 3 5.
II - The whole permutation is a framed interval which also counts as a hurdle.
III - If the hurdle 2 4 3 5 is cutted, the permutation can be reduced in (0 2 1 3 5 4 6), which still has more than one hurdle.

Select the alternative with all the CORRECT statements and no others:

a. I.
b. II.
c. III.
d. II and III.
e. None of the above.

Original idea by: Raphael Cristofaro

Week 10 - Algebraic distance, definition

Given the graph α and its inverse, choose the CORRECT statement.

Image 1 - Cycle arrow notation from a) α and b) α^-1 (extracted from Kiltinen, 2003).

a. β = (2,4,5) is a cycle that divides both α and α^-1.
b. β = (4,2,1) is a cycle that divides α but not α^-1.
c. β = (1,3,5) is a cycle that divides α but not α^-1.
d. β = α^-1 is a cycle that divides α.
e. None of the above.

References: Kiltinen, John O. Oval Track And Other Permutation Puzzles: And Just Enough Group Theory To Solve Them. Washington, D.C.: Published and distributed by the Mathematical Association of America Press, 2003.

Original idea by: Raphael Cristofaro

Week 9 - Algebraic distance, permutations

About permutations, choose the CORRECT information.

a) Let α = (a b c) and β be a 2-cycle permutation containing a, b and c. The total number of cycles in αβ will be less than the number of cycles in β.
b) Let α = (a b) and β be any permutation. If a and b are in the same cycle on the cycle decomposition of β, then this cycle will be partitioned into two on the cycle decomposition of αβ.
c) Let α = (a b) and β be any permutation. If a and b are in separate cycles on the cycle decomposition of β, they will turn into a unique cycle on the decomposition of αβ.
d) Given a permutation α, its inverse α^-1 is obtained by the inverse of the cycle decomposition of each cycle in α.
e) None of the above.

Translated by: Raphael Cristofaro
Original idea by: Kaio Karam