MO417 - Prova I2

Enunciado distribuido na sala.

Gabarito e critérios de correção:

- lim_{n → ∞}(n/2)ⁿ/n^n/2 = lim_{n → ∞}(n^1/2/2)ⁿ = ∞
  
  Logo, (n/2)ⁿ = ω(n^n/2) e (n/2)ⁿ = Ω(n^n/2). As outras letras não cabem.
- Após k arestas serem processadas, o conjunto A é uma floresta contendo árvores espalhadas mínimas para cada componente conexa do subgrafo formado por todos os vértices iniciais e pelas k arestas já processadas.
Algoritmo:
1. ordenar todos os pontos iniciais e finais juntos
  (se houver empate, colocar iniciais antes de finais)
2. fora ← true
3. comp ← 0
4. para cada ponto em ordem não decrescente faça
5. se o ponto for s[ i ] para algum i então
6. se fora então
7. // começa nova componente
8. num_int &larr 0
9. pto_inic &larr s[ i ]
10. espessura &larr 1
11. comp ++
12. senão
13. // já estamos dentro de uma componente
14. num_int ++
15. espessura ++
16. fim-se
17. senão
18. // já estamos dentro de uma componente
19. espessura --
20. se espessura == 0 então
21. // acabou componente
22. imprime "componente" comp
23. imprime "num de intervalos" num_int
24. imprime "pontos inicial e final" pto_inic f[ i ]
25. fora &larr true
26. fim-se
27. fim-se
28. fim-para
Complexidade: O(n lg n) pela ordenação, e O(n) pelo loop das linhas 4-28, dando um total de O(n lg n). Se a ordenação puder ser feita em tempo linear, então O(n) no total.
Representaremos árvores binomiais como <chave>(<lista de filhos>), omitindo listas vazias. Passos:
- 17 migra para a raiz, deslocando 15 e 7, nesta ordem.
- raiz contendo 17 é removida, dando origem a um novo heap com três árvores binomiais: 13, 7(15), 10(12,25(30)).
- o novo heap é intercalado ao antigo, dando inicialmente a coleção de árvores 5, 13, 18(20), 7(15), 3(9,14(21)), 10(12,25(30))
- árvores de raizes 5 e 13 são unidas, resultando em 5(13), 18(20), 7(15), 3(9,14(21)), 10(12,25(30))
- árvores de raizes 18 e 7 são unidas, resultando em 5(13), 7(15,18(20)), 3(9,14(21)), 10(12,25(30))
- árvores de raizes 3 e 10 são unidas, resultando em 5(13), 7(15,18(20)), 3(9,14(21),10(12,25(30)))
Desenho final:

Outras soluções são possíveis, dependendo da escolha das árvores de mesmo grau que serão unidas em alguns dos passos.
A ideia básica é executar os seguintes passos:
1. Buscar o elemento x, retornando o nó mais à direta, se houver vários nós que tenham chave x. Se x não existir na árvore, retornar o último nó visitado na busca por x.
2. Seja v o nó retornado no passo 1. Através de rotações, fazer v caminhar para cima até se tornar a raiz.
3. Fazer A₁ ← v.esq e A₂ ← v.dir. Com certeza, todas as chaves em A₁ são menores ou iguais a x e todas as chaves em A₂ são maiores que x.
4. Se a chave em v for maior que x, inserir v em A₂; caso contrário, inserir v em A₁.
A complexidade dos passos acima é O(h), O(h), O(1) e O(h), respectivamente, resultando ao final em O(h) para o algoritmo inteiro.

Estruturas adivionais necessárias: para o passo 2, se houver ponteiros para os pais ajuda muito; caso não haja, guardar o caminho da raiz até v no passo 1 para uso no passo 2.

Critérios de correção

1. Quem deu boa justificativa ganhou 1,0 ponto. Boas justificativas incluem:
  - Tirar o log dos dois lados e analisar corretamente.
  - Igualar o número de fatores e comparar cada fator.
  - Calular o limite do quociente quando n vai para infinito.
  Outros experimentaram valores. Dependendo do número de valores, ganharam:
  - 1 valor(es): 0,2 pontos.
  - 2 valor(es): 0,4 pontos.
  - 3 valor(es): 0,6 pontos.
  Quem tirou log mas concluiu errado ganhou 0,3 pontos.
  
  Demais justificativas foram consideradas fracas e não ganharam nada.
  
  Quem disse apenas Ω ou apenas ω perdeu 0,2 pontos.
2. Aqui dependeu da qualidade do invariante, como segue.
  
  Árvore espalhada mínima em cada componente: 1,0 ponto.
  
  Número de arestas em cada componente: 0,75 pontos.
  
  Subconjunto de uma árvore espalhada: 0,5 pontos.
  
  Mais leves que não formam ciclo/vértices unidos: 0,25 pontos.
  
  Demais invariantes foram considerados muito fracos e não ganharam nada. Por exemplo, quem se ateve ao histórico ao invés de se ater à situação atual (exemplo: mencionar aresta segura).
Aqui há critérios para ganhar pontos e critérios para perder pontos. Ganho de pontos:
- Algoritmo correto O(n lg n): 3,0 pontos.
- Algoritmo correto O(n²): 2,0 pontos.
- Algoritmo correto O(n³): 1,0 pontos.
- Só ideia: 0,5 pontos.
Perda de pontos (-0,3 por evento):
- Não manteve ou não atualizou corretamente atributos das componentes (núm. intervalos, inicio, fim).
- Não fechou última componente.
- Errou comparação (< em lugar de ≥, s[ i ] em lugar de f[ i ], etc.)
- Usou estrutura desnecessária (p.ex., union-find).
- Retornou componentes em vetor de tamanho n, ao invés do tamanho exato (origa o cliente a buscar as componentes no vetor).
Aqui a maioria acertou tudo. Foram apenas descontados pontos pelos seguintes deslizes:
- Não desenhou heap resultante: -0,9 pontos.
- Deixou elemento a remover (17) no heap final: -0,6 pontos.
- Ao retirar 17 de uma árvore, desmembrou a árvore demais: -0,3 pontos.
- Desenhou estruturas intermediárias que não são árvores binomiais: -0,3 pontos.
- Errou números no heap final: -0,3 pontos cada.
Aqui há critérios para ganhar pontos e critérios para perder pontos. Ganho de pontos:
- Algoritmo correto O(h): 3,0 pontos.
- Algoritmo correto O(n): 2,3 pontos.
- Algoritmo correto O(n lg n) ou O(nh): 1,6 pontos.
- Ausência de tratamento para a parte da árvore acima do nó que contém x: 1,0 pontos.
- Uso apenas de busca mais O(1): 0,7 pontos.
- Uso de estrutura não descrita ou não definida: 0,7 pontos.
- Uso de algoritmos que só funcionam em vetores (partition, busca binária): 0,7 pontos.
- Apenas esboço correto: 0,7 pontos.
Perda de pontos:
- Erro na análise por um fator ω(lg n): -0,6 pontos.
- Erro na análise por um fator O(lg n): -0,3 pontos.
- Erro em comparação (< em lugar de ≥, etc.): -0,3 pontos.

MO417 Home