MO417 - Questão para a prova oral
Numero:

Bob e Alice gostariam de troca mensagens entre eles sem que outras pessoas soubessem, assim eles estipularam o seguinte protocolo:
1. Converter toda a mensagem em representação numérica, ex: letra "A" se transforma 42.
2. Insere todas os números em uma árvore Red/Black
3. Definem em segredo qual número será a raiz e um caminhamento para a leitura desta árvore.

Desta forma, Bob envia para Alice o caminhamento pós-ordem da árvore, entretanto a mensagem, que nunca contém letras repetidas, só pode ser entendida caso seja feito o caminhamento inter-ordem para os nós a esquerda da raiz e pre-ordem para os nós a direita da raiz.  


Em relação a uma algoritmo que implementaria essa pequena confusão na mensagem, é correto afirmar.

I. Só seria atingido o balanceamento ótimo da árvore caso a mensagem fosse ordenada, com o elemento na posição mediana sendo a raiz.
II. Custo de realizar todos os três caminhamentos na árvore será sempre o mesmo independente do balanceamento da árvore.
III. A mensagem {12,9,47,27,11,5} é válida para Bob e Alice
IV.  Caso Bob enviasse  [a,b...z], para Alice, todas as varreduras resultariam na mesma mensagem, dado que a arvore seria uma "tripa", ou com todos os nós a direta do pai.


a. I e III 
b. II e IV
c. I e IV
d. II
e. N.D.A 
 

Ideia original de: Otávio Augusto Araújo Silva

MO417 - Questão para a prova oral

Numero:
 
Sobre a técnica de programação dinâmica e os problemas os quais ela se aplica, podemos dizer que:

a. Dizemos que um problema possui subestrutura ótima quando podemos dividi-lo em problemas menores cujas soluções são superpostas
b. Alguns dos problemas onde é possível utilizar a técnica de divide-and-conquer são bons candidatos para o uso da programação dinâmica caso seja garantido a independência dos subproblemas.
c. Dada a matriz A(i,p) de (sub)soluções ótimas, usada por um algoritmo que emprega a programação dinâmica, o custo deste algoritmo sempre é dominado assintoticamente por O(i*p).
d. Se a solução de um problema pode ser obtida através das escolhas das melhores soluções dos subproblemas,  podemos aplicar a programação dinâmica apenas se aquela escolha foi feita com uma abordagem top-down .
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva