Conjuntos disjuntos

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere uma matriz N x N preenchida com '0's (poros fechados) e '1's (poros abertos) aleatórios usada para modelar um material poroso. Queremos descobrir se água nos poros abertos ('1's) da primeira linha pode escorrer até a última linha passando apenas por poros abertos ('1's) adjacentes verticais ou horizontais.

1111111111111          (saída)
0001001100000
0010000110000
0100000010000          (a água escorre pelo caminho a direita
1000000011100           mas não pelo caminho a esquerda)
0100000000100
0010000000110
1111111111111          (chegada)

Para simular um material desconhecido, podemos abrir poros, isso é trocar '0' por '1', até que ele filtre, mas uma vez aberto um poro nunca muda para fechado durante uma simulação.

Sabendo que esse problema pode ser modelado usando a estrutura union-find balanceada e com compressão de caminho, considere as seguintes afirmações: 

I. Podemos responder se uma matriz fixa de entrada permite a passagem da água em O(n² lg* n²).

II. Durante uma simulação, a abertura de um poro qualquer implica em até quatro chamadas de union.

III. Durante uma simulação, uma chamada de find pode levar mais que lg* n² passos.

A) Apenas I é verdadeira.

B) Apenas II é verdadeira.

C) Somente II e III são verdadeiras.

D) Todas são verdadeiras.

E) NDA

Ideia original de: Fabrício Matheus Gonçalves

Código de Huffman

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Usando código de Huffman, qual seria uma codificação ótima para os caracteres {a, b, c, d, e, f} que aparecem com frequências {40, 20, 15, 10, 10, 5}?

A) {1, 10, 110, 1110, 11110, 11111}
B) {0, 10, 110, 1110, 11110, 11111}
C) {0, 100, 101, 110, 1110, 1111}
D) {0, 10, 101, 110, 1110, 1111}
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

Programação dinâmica

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere o problema de encontrar a rota máxima do topo até a base de um triangulo usando apenas elementos adjacentes,  x+y+d+c seria uma rota possível no triangulo:

x

y   z

a   d   e

b   c   f   g

NÃO seria correto afirmar para um triângulo com n elementos:

A) a = a + max(b, c) seria parte da estratégia para resolver o problema usando programação dinâmica bottom-up.
B) f = f + max(d, e) seria parte da estratégia para resolver o problema usando programação dinâmica top-down.
C) Com uma estratégia de programação dinâmica bottom-up podemos conseguir complexidade assintótica menor do que com uma estratégia de programação dinâmica top-down.
D) Existe um algorítimo O(2^h) que usa força bruta para calcular todas as possíveis somas, onde h é a altura do triângulo.
E) NDA

Ideia original de: Fabrício Matheus Gonçalves