Maximum flow

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Baseado na seguinte matriz de adjacências, que representa um grafo bipartido, analise as seguintes afirmações e assinale a alternativa correta:



I) O emparelhamento máximo desse grafo tem cardinalidade igual a 5.
II) As arestas (E, L) e (D, I) fazem parte de um mesmo emparelhamento máximo.
III) Esse grafo possui apenas 2 emparelhamentos máximos diferentes.

a. Somente uma das afirmações é verdadeira.
b. As afirmações I e II estão corretas.
c. As afirmações II e III estão corretas.
d. Todas as afirmações estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Single-Source Shortest Paths

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O mapa abaixo apresenta uma parte do Backbone de Internet no Brasil e ao lado é apresentada a lista de adjacências entre os roteadores, com os seus respectivos custos de envio em um determinado momento.
Assumindo que roteamento dos dados é feito apenas através do protocolo OSPF (Open Shortest Path First), que é uma implementação do algoritmo de Dijkstra, qual seria o caminho percorrido pelos dados enviados do Rio Grande do Sul (RS) para a Bahia (BA)?


a. RS, PR, SP, MG, BA
b. RS, PR, SP, RJ, ES, BA
c. RS, SC, SP, MG, DF, RJ, ES, BA
d. RS, SC, SP, RJ, DF, MG, BA
e. NDA

Ideia original de: Anderson Coelho Weller

Graph algorithms

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: A partir do grafo orientado G = (V, E), com V = {1,2,3,4,5,6} e E = {(1,3), (2,6), (3,2), (3,5), (5,1), (5,4), (6,2), (6,4)}, analise as seguintes afirmações:

I - Conseguimos tornar G um grafo fortemente conectado (conexo) invertendo o sentido de apenas uma de suas arestas.
II - Para que G tenha apenas dois componentes fortemente conectados, faz-se necessário inverter o sentido de, no mínimo, duas de suas arestas.
III - É possível obter uma ordenação topológica para o grafo G, caso sejam removidas duas de suas arestas.

Assinale a alternativa correta:

a. I e II estão corretas.
b. I e III estão corretas.
c. II e III estão corretas.
d. I, II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Red-black Trees

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um dicionário futebolístico é indexado através de uma árvore Vermelho-Preto, onde cada nó é um ponteiro para uma lista de palavras iniciadas com a mesma letra.
Antes de inserir uma palavra no dicionário, o sistema verifica se o nó com a chave correspondente já está na árvore, se não estiver ele usa o método RB-INSERT abaixo para incluí-lo.
Sabendo que foram inseridas apenas as seguintes palavras no dicionário (Na mesma ordem em que são apresentadas), responda: Qual das alternativas abaixo está correta?

Futebol - Liga - Atacante - Meia - Equipe - Número - Goleiro - Obstrução

RB-INSERT(T, z) 01  y = T.nil 02  x = T.root 03  while (x != T.nil) { 04     y = x 05     if (z.key < x.key) 06          x = x.left 07     else x = x.right 08  } 09  z.p = y 10  if (y == T.nil) 11  {  T.root  = z } 12  elseif (z.key < y.key) 13  {  y.left  = z } 14  else 15  {  y.right = z } 16  z.left  = T.nil 17  z.right = T.nil 18  z.color = RED 19  RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z) 01 while (z.p.color == RED) { 02    if (z.p == z.p.p.left) { 03       y = z.p.p.right 04       if (y.color == RED) { 05          z.p.color = BLACK 06          y.color   = BLACK 07          z.p.p.color = RED 08          z = z.p.p 09       } else { 10          if (z == z.p.right) { 11             z =  z.p 12             LEFT-ROTATE(T, z) } 13          z.p.color = BLACK 14          z.p.p.color = RED 15          RIGHT-ROTATE(T, z.p.p) } 16    } else { 17    /* Código igual a cláusula "then" 18     com "right" e "left" trocados.*/ } 19 } 20 T.root.color = BLACK

a. A altura de preto dessa árvore é 3.
b. O número de nós internos na cor preta é superior aos de cor vermelha.
c. Os nós com as chaves "G", "O" e "L" possuem a mesma cor.
d. Os nós com as chaves "F", "L" e "A" ficaram em níveis diferentes.
e. NDA

Ideia original de: Anderson Coelho Weller

Greedy Algorithms

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um arquivo bitmap, contendo um conjunto de 100 pixels, foi compactado através do algoritmo de Huffman. Seguindo a quantidade de pixels por cor (existentes nesse arquivo) e o algoritmo gerador do código de prefixo de Huffman, apresentados abaixo, responda:
Qual é o tamanho (em bits) desse conjunto de pixels após a compactação?

COR	Red	Green	Blue	Black	White	TOTAL
Número de Pixels	5	10	15	20	50	100

Huffman(Cores)    n = Cores.lenght    Q = Cores    for i = 1 to n-1       Aloca um novo nó 'z'       z.esquerda = x = Extrair-Menor(Q)       z.direita  = y = Extrair-Menor(Q)       z.pixels   = x.pixels + y.pixels       Inserir-Ordenado(Q, z)    return Extrair-Menor(Q) // Retorna a raiz da árvore

a. 175
b. 180
c. 195
d. 200
e. NDA

Ideia original de: Anderson Coelho Weller

Dynamic programming

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Comparando os métodos "Dividir e Conquistar" e "Programação Dinâmica", qual das alternativas abaixo está INCORRETA:

a. Ambos resolvem problemas combinando as soluções para subproblemas.
b. Comparado com o método de "Programação Dinâmica", algoritmos "Dividir e Conquistar" trabalham mais do que o necessário, resolvendo repetidamente subproblemas comuns.
c. Algoritmos "Dividir e Conquistar" particionam o problema em subproblemas independentes, resolvem-nos recursivamente, e combinam suas soluções para resolver o problema pricipal.
d. A ideia principal da "Programação Dinâmica" é resolver cada subproblema apenas uma vez, salvar suas respostas em uma tabela, evitando assim o trabalho de recalcular a resposta cada vez o subproblema é encontrado.
e. NDA

Ideia original de: Anderson Coelho Weller

Dynamic programming

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dada as sequências X=< S, U, S, S > e Y = < A, S, S, E, S, S >, é fácil visualizar que a LCS (Longest Common Subsequence) delas é < S, S, S >. Porém, como fica a ligação entre as letras da sequência Y com as letras da sequência X?

a.		A	S		S	E	S	S
			S	U	S		S
b.		A	S		S	E	S	S
			S	U	S			S
c.		A	S		S	E	S	S
			S	U			S	S
d.		A	S	S	E		S	S
				S		U	S	S

e.

NDA

Ideia original de: Anderson Coelho Weller

Order statistics

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as seguintes afirmações:

I - Para localizar o maior valor em uma lista desordenada são necessárias, no mínimo, n-1 comparações entre seus n elementos.
II - Para encontrar o segundo maior valor em uma lista com n elementos, são necessárias n + ⌈ lg n ⌉ - 1 comparações no pior caso.
III - Comparando-se aos pares, os n elementos de uma lista, até que sobre apenas o menor valor, gera um total mínimo de ⌊ n^{(1+1/lg n)}⁄ 2 ⌋ - 1 comparações.

Assinale a alternativa correta:

a. Apenas I está correta.
b. I e II estão corretas.
c. I e III estão corretas.
d. II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Linear time sorting

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Supondo que, utilizamos o Radix-Sort para ordenar n-números inteiros, com o tamanho máximo de b-bits. Avalie as seguintes afirmações, sabendo que esse algoritmo ordena os números no tempo de Θ((b/r)(n+2^r)) para qualquer valor inteiro positivo r ≤ b:

I - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a nⁿ-1.
II - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a n³-1.
III - Para chegar a esse limite assintótico é necessário ordenar os d-digitos através de um método estável, como o Merge-Sort.

a. Apenas I está correta.
b. Apenas II está correta.
c. I e II estão corretas.
d. I, II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Recurrences

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as seguintes recorrências, assinale a alternativa correta:

T₁(n) = 5T(n/6) + n²
T₂(n) = 5T(n/2) + n^{lg 5}
T₃(n) = 5T(n/2) + n²

a. T₁(n) possui uma ordem de crescimento maior do que T₂(n)
b. T₂(n) possui uma ordem de crescimento maior do que T₃(n)
c. T₃(n) = Θ(n^{lg 5} lg n)
d. T₁(n) = Θ(n^{log₆ 5})
e. NDA

Ideia original de: Anderson Coelho Weller

Growth of functions

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado um algoritmo com a mesma estrutura apresentada abaixo, cujo laço externo executa f(n) = 7n vezes um laço interno e este último executa g(n) = lg n vezes um bloco de complexidade h(n) = 10n². Qual é o "Limite assintótico superior" dele?

Repetir f(n) vezes
{
    Repetir g(n) vezes
    {
       Repetir h(n) vezes
    }
}

a. O( 10n² )
b. O( n³ )
c. O( n² )
d. O( n³ lg n )
e. NDA

Ideia original de: Anderson Coelho Weller