1. Considere as seguintes funções:
   
   
   1. 10.n^p
   2. log n
   3. log ( n² )
   4. 0.005 . n^0.00001
   5. 1000. (log n)²
   6. 30.n³.log n
   7. 50.n.log² n
   8. (log n)^{log n}
   9. n/log n
   10. 70.n
   11. log log n
   12. (1.5)^{(log n)2}
   13. 90.n².log n + n³. log n
   
   
   • Coloque as funoeacima em ordem de crescimento assintótico, i.e. valor
     quando n ¾® ¥.
     
     
   • Utilize pelo menos três vezes cada um dos símbolos O,    W,    Q,    o, e w para indicar a relação existente entre pares das funoeacima (não vale recíprocos).
   
   
2. Encontre contra-exemplos para as proposições abaixo.
   1. Se f(n) = O(s(n)) e g(n) = O(r(n)), então f(n) - g(n) = O(s(n)-r(n))
   2. Se f(n) = O(s(n)) e g(n) = O(r(n)), então f(n)/g(n) = O(s(n)/r(n))
   
   
3. 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.
   
   
4. 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?
   
   
5. Verdadeiro ou Falso. Justifique.
   1. (log n)¹⁰⁰ = O(n^e), " e > 0.
   2. 2ⁿ⁺¹ = O (2ⁿ).
   3. Se g(n,m) = m log_d n onde d = [ m/n + 2] ( [x] é o menor inteiro maior que x), m = O(n²), então g(n,m) = O(m^{(1 + e)}) " e > 0.
   
   
6. Determine uma forma fechada para cada uma das seguintes recorrência:
   
   
   1. T(1) = 1;
      
      T(2) = 6;
      
      T(n) = T(n-2) + 3n + 4, " n ³ 3.
      
      
   2. T(1) = 1;
      
      T(2) = 6;
      
      T(n) = 2.T(n-2) + 3, " n ³ 3.
      
      
   3. T(1) = 1;
      
      T(n) = å_i=1^n-1 (T(i) + T(n-i)) + 1, " n ³ 2.
   
   
7. 
   
   Seja S = {x₁, x₂, ... , x_n } uma seqüência de números reais (não necessariamente positivos). Projete dois algoritmos de complexidade O(n), um iterativo e um que utilize divisão e conquista (ambos podem ser recursivos!), que determine uma subseqüência S' = {x_i, x_i+1, ... , x_j} de elementos consecutivos da seqüência S tal que o produto dos números que compõem S' é máximo dentre todas as subseqüências consecutivas possíveis.
   
   
8. 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.
   
   
9. Dados um multiconjunto C contendo n números reais (não necessariamente distintos) e um número real x:
   1. Projete um algoritmo de complexidade O(n log n) que determine se existem dois elementos em C cuja soma seja igual a x.
   2. Considere agora que os elementos do conjunto C estão ordenados crescentemente. Projete um algoritmo de complexidade O(n) para resolver o mesmo problema.
   
   
10. O departamento de transporte de uma cidade deseja averiguar se seus motoristas respeitam os conceitos pregados pela técnica de direção defensiva. De acordo com o departamento, todos os veículos deveriam manter entre si uma distância maior ou igual d, definida como distância de segurança. Com o objetivo de realizar uma pesquisa, várias câmeras foram instaladas pela cidade, captado as posições de inúmeros veículos. A posição de um veículo é definida por um par ordenado (x,y) Î R². Seu objetivo é projetar um algoritmo de complexidade O(n log n) que obtenha uma cena contendo as posições de n veículos captadas por uma câmera e a distância de segurança d atualmente estabelecida pelo departamento, informando ao final da execução se existem veículos que não respeitam a distância de segurança. Seu algoritmo deve responder apenas sim ou não. A distância entre dois veículos com posições (x₁,y₁) e (x₂,y₂) é dada por (x₂ - x₁)² - (y₂ - y₁)².
    
    
    
11. O problema da torre de Hanói generalizado consiste em mover n discos de diâmetros distintos, posicionados em um haste denominada origem, para uma haste denominada destino utilizando m ³ 1 hastes denominadas de trabalho. Inicialmente, todos os discos encontram-se empilhados na haste de origem em ordem decrescente de tamanho, de baixo para cima. As demais hastes de trabalho e destino encontram-se vazias. Durante o processo de transferência é permitida a movimentação de apenas um disco por vez. Considere ainda que nenhum disco pode ser posicionado acima de um disco com diâmetro menor que o seu. Projete um algoritmo que resolva o problema da torre de Hanói generalizado utilizando o menor número de movimentos possível. Seu algoritmo deve relatar a ordem e a quantidade de movimentos a serem realizados.
    
    
12. Seja uma sequência de n inteiros distintos T = { t₁, ..., t_n }. Uma subsequência crescente de T é um subconjunto não necessariamente consecutivo de T que preserva a ordem em T.
    
    
    1. Considere o problema de encontrar a subsequência (não necessariamente consecutiva) crescente de T com maior número de elementos.
       
       Defina T(j) como a sequência { t₁, ..., t_j }. Assuma que para um dado j, j £ n, conhece-se as subsequências de tamanho k, 0 £ k £ j (k não necessariamente vai até j), cujo último elemento tem o menor valor possível.
       
       Projete o algoritmo resultante da obtenção destas subsequências cada vez um novo elemento de T é considerado (j é incrementado). Analise a complexidade do algoritmo obtido. O seu algoritmo deve ter complexidade O(n²).
       
       
    2. Considere, agora, que para cada elemento de T é associado um custo positivo c_i, i=1,...,n. Proponha um algoritmo para encontrar a subsequência crescente de T onde a soma dos custos dos elementos é maximizada.
       
       Dica: Qual seria o custo em que esse problema fica equivalente ao do item (a).
       
       
    3. Mostre como os algoritmos obtidos acima funcionam na sequência: 3, 17, 9, 12, 35, 6, 27, 8, 21, 26, 23, 11, 19, 13, 15. Execute o algoritmo do item (b) (só até o sexto elemento) com os custos 1, 2, 3, 4, 5, 6 e também com os custos 15, 14, 13, 12, 11, 10.
       
       
    4. Analise a complexidade do algoritmo em (b). Diga se ele tem complexidade polinomial ou exponencial. No caso da resposta ser exponencial, indique se a complexidade é pseudo-polinomial.
       
       
    5. O problema do item (b) pode ter algoritmo polinomial ? No caso afirmativo, apresente um algoritmo polinomial. No caso negativo justifique.
    
    
13. Sejam S₁ e S₂ conjuntos cujos elementos são números inteiros e onde |S₁|=|S₂|=n.
    1. Escreva um algoritmo para determinar a união de S₁ e S₂. Nenhum elemento deve aparecer mais de uma vez. Analise sua complexidade em função de n (melhor caso e pior caso).
    2. Este algoritmo deve executar em O(n log n).
    
    
14. Seja uma função convexa f(x) definida no intervalo [0,U]. Dado um e > 0, deseja-se encontrar x⁰ de modo que o intervalo [ x⁰ - e, x⁰ + e ] contenha x^* onde f(x^*) é o menor valor de f no intervalo dado.
    
    
    1. Suponha que, para um dado x e um dado U, o cálculo de f(x) se faz em tempo constante. Projete um algoritmo de complexidade O(log (U/ e )).
       
       Dica: Lembre que a função é covexa e, para iterativamente se aproximar do mínimo, determine o valor da função em 4 pontos. O que você pode concluir sobre onde está o mínimo de f ?
       
       
    2. A complexidade deste algoritmo é polinomial ? Justifique.
    
    
15. Considere que os n itens de uma busca arqueológica estão organizados nos andares de uma pirâmide de modo que o item de maior valor está no andar mais alto, os 2 itens de maior valor seguintes estão no andar abaixo, os 4 itens de valores menores no andar abaixo do que tem 2 itens, e assim por diante. Isto é, sendo v₁, v₂, ..., v_n e que v₁ ³ v₂ ³ v₃ ³ ... ³ v_n, o item 1 está no andar mais alto, 2 e 3 no seguinte, os itens 4, 5, 6 e 7 logo abaixo, e assim por diante. Responda:
    1. Quantos andares tem a pirâmide que guarda os itens ?
    2. Utilizando um vetor para armazemar o valor do item de maior valor de cada andar da pirâmide, proponha um algoritmo O(log log n) para determinar o andar em que se encontra um item dado.
    
    
16. Analise a eficiência do algoritmo abaixo, calculando o número de passos executados pelo mesmo em função de um número n fornecido como entrada. Considere que todas as operações básicas envolvidas (atribuição, operações lógicas, operações aritméticas, entrada/saída) possuem custo constante (c = O(1)).

    
    Leia(n);
    x <- 0;
    Para i <- 1 até n faça
       Para j <- i+1 até n faça
          Para k <- 1 até j-i faça
             x   x + 1;
    Imprima(x);
    

17. Perdido em uma terra muito distante, você se encontra em frente a um muro de comprimento infinito para os dois lados (esquerda e direita). Em meio a uma escuridão total, você carrega um lampião que lhe possibilita ver apenas a porção do muro que se encontra exatamente à sua frente (o campo de visão que o lampião lhe proporciona equivale exatamente ao tamanho de um passo seu). Existe uma porta no muro que você deseja atravessar. Supondo que a mesma esteja a n npassos de sua posição inicial (não se sabe se à direita ou à esquerda), elabore um algoritmo para caminhar ao longo do muro que encontre a porta em O(n) passos. Considere que n é um valor desconhecido (informação pertencente à instância). Considere que a ação composta por dar um passo e verificar a posição do muro correspondente custa O(1).
    
    
18. ``Pseudo ou não-pseudo? Eis a questão.''
    
    
    1. Defina os conceitos de algoritmo polinomial e algoritmo pseudopolinomial.
       
       
    2. Forneça um exemplo de um algoritmo polinomial e outro de um algoritmo pseudopolinomial.
       
       
    3. Prove ou refute: Todo algoritmo polinomial é pseudopolinomial.
       
       
    4. Prove ou refute: Todo algoritmo pseudopolinomial é polinomial.
    
    
19. Era uma vez um rei que não conhecia algoritmos. Durante um fatídico verão, seu reino fora invadido por um dragão, obrigando os conselheiros da ordem omega-theta a se reuniram e decidirem por contratar o cavaleiro mais corajoso (e ambicioso) do reino que fez uma proposta de recompensa associada ao peso do animal. Considerando que o peso do dragão seja n quilos, a cobrança será feita em moedas de ouro, seguindo a regra de k . 2 (n-k) moedas de ouro adicionais para o k-ésimo quilo do dragão. Para exemplificar, um dragão com 4 quilos custaria ao reino 1 . 23 + 2 . 22 + 3 . 21 + 4 . 20 = 26 moedas de ouro.
    
    Elabore um algoritmo POLINOMIAL (LINEAR!!!) que, dado um inteiro positivo n, correspondente ao peso do dragão, calcule a quantidade de moedas a serem pagas ao cavaleiro. O algoritmo (projetado para ser executado pelos conselheiros da corte) deve conter apenas as operações aritméticas de soma, subtração, multiplicação e divisão de inteiros (considere que qualquer uma dessas operações é realizada em tempo constante).
    
    
20. No que se refere ao conceito de esquema de codificação de uma instância:
    
    
    1. Prove por indução que um número inteiro positivo n ao ser codificado na base b 2 faz uso de (log b n) caracteres.
       
       
    2. Prove por indução que um número inteiro positivo n ao ser codificado na base unária faz uso de (n) caracteres.
       
       
    3. Utilizando o resultados anteriores prove que, um algoritmo que recebe como entrada um número inteiro positivo n codificado em uma base b 2 e que executa em n passos é um algoritmo de complexidade exponencial em função do tamanho da instância.

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