Fluxo Máximo

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: O grafo abaixo representa o fluxo em uma rede de capacidade infinita para todas as arestas. Qual dos seguintes pares de vértices NÃO respeitam a propriedade de conservação do fluxo?

A) b, c
B) d, e
C) b, d
D) c, e
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

Caminhos mais Curtos

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Qual a diferença entre o custo total da árvore espalhada mínima e o custo total da árvore com caminhos mínimos a partir do vértice A até todos os outros vértices do grafo abaixo?

A) 0
B) 1
C) 2
D) 3
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

Árvores Geradoras Mínimas

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere as seguintes afirmações relativas ao problema de encontrar uma árvore geradora mínima (AGM) de um grafo G = (V, E):

I. Supondo que o peso das arestas são inteiros de 1 a |V| é possível usar Counting Sort com o algoritmo de Kruskal para obter uma AGM em O(Eα(V)).

II. Quando |E| = Ω(V lg V), o algorítimo de Prim, implementado usando heap de Fibonacci, obtem uma AGM em O(E).

III. Não existe algorítimo que encontre uma AGM em tempo linear.

A) Todas são verdadeiras.
B) Apenas I é verdadeira.
C) Somente I e II são verdadeiras.
D) Somente I e III são verdadeiras.
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

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

Uso de memória em algorítimos de ordenação

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Com relação ao uso de memória, incluindo a memória usada na pilha em chamadas recursivas, NÃO é correto afirmar que:

A) O Quicksort pode ser otimizado para usar apenas O(lg n) de espaço extra.
B) O Heapsort pode ser implementado para usar apenas O(1) espaço extra.
C) O Merge sort pode ser implementado usando lista ligada para usar apenas O(lg n) espaço extra.
D) O Counting sort pode ser implementado usando O(n) espaço extra, se o intervalo dos números a serem ordenados também for O(n).
E) NDA

Ideia original de: Fabrício Matheus Gonçalves