1. Dado um grafo não-orientado G=(V,E) e pesos w_e, e Î E, associados às arestas, proponha algoritmos, com suas respectivas estruturas de dados, para as seguintes operações:
   1. Dado um conjunto X Ì V, encontrar o valor do corte definido por X: å_{(i,j)| i Î X j Î V-X}w_(i,j). Isto é, a soma dos pesos associados às arestas com uma extremidade em X e outra em V-X.
   2. Calcular o novo valor de um corte quando um elemento, j, é retirado do conjunto X. A complexidade deve ser O(n²). Explique por que essa operação é W (n²).
   3. Obter o elemento (vértice) cuja retirada do conjunto X impõe a maior redução sobre o valor do corte. Qual a complexidade de se obter a variação no valor do corte para a saída de cada vértice.
   4. Dado que as variações estão disponíveis, antes da retirada de um dado vértice, proponha um algoritmo O(n) para determinar as variações (para todos os vértices) após a retirada do vértice dado.
   5. Proponha um algoritmo para fazer a retirada sucessiva de todos elementos em X, a cada iteração retira-se sempre o que corresponde à maior redução (ou menor aumento, caso não seja possível uma redução). O algoritmo deve executar em O(n²).
   6. Repita os itens acima para a inclusão dos elementos que não estão em X.
   7. Repita agora os itens acima para a inclusão dos elementos que não estão em X e a exclusão dos que não estão.
   
   
2. Apresente um algoritmo para transformar o problema (MC) no problema (MS) em tempo linear.
   
   Clique-Máximo (MC) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um clique (isto é um sub-grafo completo) de cardinalidade maior ou igual à K.
   
   Estável-Máximo (MS) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um conjunto de vértices independentes (isto é, um conjunto de vértices onde não existe aresta entre nenhum par do conjunto) de cardinalidade maior ou igual à K.
   
   
3. Apresente um algoritmo para transformar o problema (PART) no problema (KP) em tempo linear.
   
   (PART) Instância: Dado um conjunto de elementos X={x₁, x₂, ..., x_n} e seu respectivos tamanhos T={t₁, t₂, ..., t_n }.
   
   Questão: Existe um subconjunto S de X tal que å_{xi Î S} T_i = å_{xi Î X-S} T_i ?
   
   (KP) Instância: Dado um conjunto de elementos X={x₁, x₂, ..., x_n}, seus respectivos tamanhos T={t₁, t₂, ..., t_n } e seus respectivos valores V={v₁, v₂, ..., v_n }, e as constantes T₀ e V₀.
   
   Questão: Existe um subconjunto de S de X tal que a soma dos tamanhos dos elementos em S seja menor ou igual a T₀ e tal que a soma dos seus respectivos valores seja superior ou igual a V₀ ?
   
   
4. Considere o algoritmo de Dijkstra para encontrar o caminho mais curto entre um vértice fonte e os demais vértices de um grafo orientado G=(V,E) onde a distância associada a um arco e Î E é dada por l_e = l_vw onde v e w são o vértice de partida e de chegada do arco e, respectivamente. (As complexidades devem ser obtidas em função de n=|V| e m=|E|).
   
   Algoritmo Dijkstra (s - fonte)
   • Passo 0: Inicialização
     
     Seja S o conjunto de vértices com caminho mais curto a partir de s determinado, e S seu complemento (S = V - S).
     
     S ¬ Ø
     
     d(i) ¬ +¥ " i Î V;
     
     d(s) ¬ 0; pred(s) ¬ 0;
     
     
   • Passo 1: Iteração
     • Enquanto S Ì V faça
       
       
       • 1.1 Encontre v Î S t.q. d(v) = min_{w Î S} d(w)
         
         
       • 1.2 S ¬ S È { v }; S ¬ S \ { v };
         
         
       • 1.3 Para todo w Î G⁺ (v)
         
         Se d(v) + l_vw < d(w)
         
         então d(w) ¬ d(v) + l_vw; pred(w) ¬ v;
   
   Responda aos itens abaixo:
   1. Considere que o passo 1.1 é realizado através do uso de um vetor que armazena os valores d(i), i=1,...,n. Qual a complexidade deste passo (uma execução) ? Qual a complexidade total (soma de todas as execuções) deste mesmo passo (1.1) ?
   2. Repita esta análise para os passos (1.2) e (1.3).
   3. Qual a complexidade global desta implementação do algoritmo de Dijkstra ?
   4. Onde poderia ser usada uma heap ? Por que isso poderia ser bom ?
   
   
5. Sejam P₁, P₂ e P₃ três problemas tais que P₁ a_n P₂ a_n³logn P₃ (i.e., P₁ é redutível a P₂ em tempo linear e P₂ a P₃ em tempo n³ log n). Assuma a hipótese de que P₁ é W(n log n). Assuma também que você conhece um algoritmo O (n³) para resolver P₃.
   
   Discuta as afirmações abaixo.
   1. O que você pode dizer sobre a complexidade de resolução de P₂ ? Qual a complexidade do melhor algoritmo que você conhece para P₂ ?
      
      
   2. Todo algoritmo que resolve P₂ tem que gastar pelo menos tempo quadrático (P₂ é W(n²)).
      
      
   3. W(n log n) é um limite inferior para a complexidade de P₃.
      
      
   4. P₂ pode ser resolvido no pior caso em tempo O(n log n).
   
   
6. Considere uma árvore T=(V,E) com distâncias d_e associadas às arestas. Deseja-se construir uma matriz n × n contendo as distâncias entre cada para de vértices sobre T. Considere que T é dada no formato de lista de adjacência. Deseja-se um algoritmo O(n²) para se construir a matriz de distâncias.
   
   
7. Suponha que 2n alunos querem entrar em n universidades. Cada universidade vai receber no máximo 2 alunos e você conhece a lista de universidades que aceitaram cada aluno. Deseja-se alocar os alunos às universidades de modo que o máximo de alunos ingressem nas universidades. Formule esse problema como um problema de Alocação/Emparelhamento em um grafo bi-partido. Lembre que você deve especificar uma instância do problema de Alocação que resolve esse problema, isto é, definir a matriz de custos de atribuição.
   
   
8. Considere o seguinte problema: (CMG) Caminho de menor Gargalo: Dado um grafo não-orientado G=(V,E) com distâncias d_e associadas às arestas, e um vértice r, determinar os caminhos de r a todos os demais vértices, cuja maior aresta é o menor possível.
   
   Transforme o problema de encontrar a Árvore Geradora Mínima em grafo no problema (CMG).
   
   
9. Considere um grafo não-orientado G=(V,E) com pesos w_e associados às arestas. Um conjunto F Í E é chamado de conjunto de arestas de realimentação se todos os ciclos em G contém pelo menos uma aresta de F. Deseja-se encontrar o conjunto F de menor peso.
   
   Transforme este problema no de encontrar a árvore geradora de peso máximo (dê um algoritmo para esse problema).
   
   Dica: Observe que o grafo obtido retirando as arestas em F de G=(V,E) não pode conter ciclos (por que ?).

This document was translated from L^AT_EX by H^EV^EA.