1. Considere uma heap com n inteiros e um valor x. A heap possui o seu maior elemento no topo e está organizada em um vetor (de n posições). Proponha um algoritmo para decidir se o valor x é maior ou igual ao k-ésimo maior elemento na heap ou não. O algoritmo deve executar em O(k).
   
   Dica: Observe que você não precisa necessariamente encontrar o k-ésimo maior elemento da heap.
   
   
2. Considere o seguinte problema:
   
   [ELE] Dados um conjunto de n inteiros distintos X={ x₁, ..., x_n} e pesos positivos w(x_j), j=1,...,n, associados aos elementos de X, e um inteiro positivo V tal que 0 £ V £ W = å_j=1ⁿ w(x_j); encontrar o elemento x_k tal que å_{xj < xk} w(x_j) < V e w(x_k) + å_{xj < xk} w(x_j) ³ V.
   
   
   1. Projete um algoritmo O(n log n) para resolver esse problema.
   2. Utilize divisão e conquista para projetar um algoritmo O(n) para resolver esse problema.
   3. Apresente detalhadamente a análise da complexidade do item anterior.
   
   
3. Sejam u e v dois números de n bits (considere que n é potência de 2). A multiplição tradicional de u por v utiliza O(n²) operações. Um algoritmo baseado em divisão e conquista divide os números em duas partes iguais, calculando o produto como: uv = (a2^n/2+b)(c2^n/2+d) = ac2ⁿ + (ad + bc)2^n/2 + bd. As multiplicações ac, ad, bc e bd são feitas usando este mesmo algoritmo recursivamente.
   • Escreva este algoritmo
   • Determine a complexidade
   • Qual é a complexidade se ad + bc é calculado como (a + b)(c + d) - ac - bd?
   
   
4. Prove que os problemas abaixo pertencem a NP, ou explique porque não se sabe, ou porque não pertence a NP. Para provar que pertence à NP, apresente o certificado e justifique porque a verificação do SIM é feita em tempo polinomial.
   1. Hemisfério Aberto
      
      Instância: Um conjunto finito de n m-tuplas X={ x₁=<x₁¹, x₁², ... x₁^m>, x₂, ..., x_n } e um inteiro K £ n.
      
      Pergunta: Existe uma m-tupla y=<y¹, y², ... y^m> tal que o produto interno entre y e x é maior que zero, isto é y.x >0, para pelo menos K m-tuplas x Î X ?
      
      
   2. K Caminhos mais curtos.
      
      Instância: Um grafo orientado G=(V,E), as distâncias positivas dos arcos e, _e, para e Î E, um par de vértices de V, s e t, e inteiros positivos L e K.
      
      Pergunta: Existem K caminhos de s a t em G tais que sua distância total não ultrapassa L ?
      
      
   3. Equações Diofantinas Quadráticas.
      
      Instância: Inteiros positivos a, b e c.
      
      Pergunta: Existem inteiros positivos x e y tais que a.x² + b.y = c ?
      
      
   4. Atribuição Sequencial V/F
      
      Considere o seguinte jogo entre dois jogadores. Dada um instância do problema 3-SAT, os jogadores atribuem V ou F às variáveis em um sequência pré-fixada. Na primeira rodada o jogador 1 atribui V ou F à variável u₁ e o jogador 2 à variável u₂, na segunda, 1 à u₃ e 2 à u₄. Na i-ésima jogada, 1 à u_2i-1 e o jogador 2 à u_2i. O jogador 1 vence se todas as cláusulas forem satisfeitas. Considere agora o seguinte problema:
      
      Instância: Uma sequencia de variáveis lógicas U={ u₁, u₂, ..., u_n } e uma coleção de cláusulas de tamanho 3, C={ c₁(u), c₂(u), ..., c_n(u) }
      
      Pergunta: O jogador 1 vence o jogo ? Ou seja, existe um sequência de decisões para o jogador 1 em que ele vence o jogo independente das ações do jogador 2 ?
   
   
5. Considere os seguintes problemas:
   • Vertex Cover (VC): Dados um grafo (não orientado) G=(V,E) e um inteiro positivo K £ |V|; determinar se existe S Ì V, |S| £ K, tal que para toda aresta (u,v) Î E, pelo menos um entre u e v, pertence a S.
     
     
   • Dominating Set (DS): Dados um grafo (não orientado) H=(N,A) e um inteiro positivo L £ |N|; determinar se existe U Ì N, |U| £ L, tal que para todo vértice w Î N \ U existe um vértice u Î U tal que (u,w) Î A.
     
     
   • Uncapacitated Facility Location (UFL): Dados conjuntos M e N, inteiros c_ij para i Î M e j Î N, inteiros f_j para j Î N e um inteiro T; determinar se existe um conjunto J Í N tal que å_{i Î M} min_{j Î J} c_ij + å_{j Î J} f_j £ T.
   
   
   1. Sabendo que (VC) é NP-comleto (foi provado em aula!), prove que (DS) também é NP-completo.
      
      Dicas: Observe que todo VC é um DS. Pense em formas de obrigar que um DS também seja um VC, ou seja se cobrir todos os vértices no grafo do problema (DS) (o grafo H) então cobre todas a arestas da instância (o grafo G) do problema VC.
      
      
   2. Sabendo que (VC) é NP-comleto (foi provado em aula!), prove que (UFL) também é NP-completo.
      
      Dicas: Observe que, se for interpretado que o (UFL) é definido sobre um grafo, este grafo tem dois tipos de vértices.
      
      
   3. Considere a seguinte instância do (VC): G=(V,E) onde V={1, 2, 3, 4, 5}, e E = { (1,2), (1,4), (2,3), (3,4), (1,5), (2,5), (3,5), (4,5) } e seja K = 3. Utilize as transformações que você propôs nos itens anteriores para obter instâncias equivalentes do (DS) e do (UFL).
   
   
6. Considere o problema (VC) Vertex Cover definido na questão anterior. Seja o algoritmo abaixo para resolvê-lo.
   • Algoritmo RVC
   • P0 Faça RESPOSTA igual a NÃO.
   • P1 Para cada subconjunto S de K vértices dos vértices em V faça:
     • P1.1 Teste se S é um Vertex Cover.
       
       No caso afirmativo faça RESPOSTA igual a SIM, retorne RESPOSTA.
       
       No caso negativo, vá para o próximo subconjunto.
   • P3 Retorne RESPOSTA.
   1. Demonstre que a complexidade do algoritmo RVC acima é O(n^K) onde n=|V|.
   2. Esta complexidade é polinomial ? (Se é, por que não implica que P = NP ?)

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