Prova AA
Questão 1
A)
Inv0
For i=1 ... N-1
For J=2...N
If A[i]>A[j]
inv++
Questão 1
B) Criamos um vetor B de k posições inicialmente
zerado e executamos os seguinte pseudo-código de
complexidade O(nk) que é superior a O(n^2) para k
sublinear
Inv0
Para i=1..N
B[A[i]]++
Para j=A[i]+1 ... K
InvInv+B[j]
Questão 2
A complexidade do pseudo-código em função de
cé
n^{1/2} + (n^{1/2} / c) *n
A) Para c=2 temos O(n^{3/2})
B) Para c= (n^{1/2})/2 temos O(n)
Questão 3
Monte um grafo direcionado G onde cada atividade é um
nó e cada par de L é uma aresta direcionada. Basta testar
se as seguintes condições são válidas
a) a_1 é uma fonte
b) a_n é um sumidouro (sink)
c) G tem ordenação topológica
Os itens a) e b) podem ser realizados em O(m+n)
percorrendo a lista dde adjacências do grafo. O item c)
pode ser realizado em O(m+n) com o algoritmo
apresentado em sala.
Questão 4
Pseudo código:
• Antes de chamar DFS-VISIT em main
d(s)0 e altura0
• Em DFS-VISIT
Linha 3.5 d(v)=d(u)+1
Linha 3.7 altura max{altura,d(v)}
A altura não representa o maior caminho que tem
início em s. Desenhar contra-exemplo
Questão5
• Para resolver esta questão basta encontrar uma aresta
que não pertence ao grafo tendo em vista que o grafo
é conexo.
• Isso pode ser feito em O(m+n), percorrendo a lista de
adjacências do grafo. Ao encontrar um vértice v com
menos que n-1 arestas, percorra a lista de adjacência
de v novamente e anote em um vetor cada vértice que
é vizinho de v. Se o vértice u não for anotado então a
aresta uv é solucão do problema.
• Se todo vértice v tiver n-1 vizinhos (grafo completo)
então tal aresta não existe.
Correção
• Corrigir provas é uma das tarefas mais
desagradáveis da vida acadêmica.
• Corrigir provas toma bastante tempo e eu
procuro gastar uma energia considerável para
ter uma correção “justa”
• Eu dei alguns pontos de bonus na correção
Portanto,
Correção
• Não “chorem” pontos. A minha tendência é
diminuir os pontos dados se eu entender que a
solicitação não tem fundamento. A premissa “vou
pedir pontos porque não me custa nada” não é
falsa. Ela pode custar caro
• Soluções que eu não entendo após refletir por
um ou dois minutos eu atribuo uma nota baixa.
Não é viável passar horas tentando entender uma
solução. Se você quer ter mais confiança se sua
solução (algoritmica) funciona ou não, sugiro que
implemente ela e teste para vários casos.
Correção
• Se não concordar com a revisão me entregue
uma folha com a solicitação de revisão e o
motivo