1. Considere as seguintes funções:
   1. 10.n^p
   2. log n
   3. log ( n² )
   4. 30.n³.log n
   5. 50.n.log² n
   6. (log n)^{log n}
   7. n/log n
   8. 70.n
   9. log log n
   10. 90.n².log n + n³. log n
   • Coloque as funções acima 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 funções acima (não vale recíprocos).
   
   
2. Seja f_i(n) o número de operações realizadas pelo programa i abaixo(log logaritmo na base 2).
   • Obtenha f_i(n) em função de n e de grupos de operações que demandam tempo constante (para os quais você pode utilizar símbolos c₁, c₂, ... para indicar esse número constante de operações). Caso existam valores indeterminados, cosidere-os como variáveis e dê o intervalo de valores que esta pode assumir.
   • Encontre funções l_i(n) e u_i(n) tais que f_i(n) = W(l_i(n)) (a maior possível) e f(n) = O(u_i(n)) (a menor possível).
   • Indique quando existe uma função h_i(n) tal que f_i(n) = Q (h_i(n)).
   • Caso o algoritmo seja recursivo, escreva sua relação de recorrência. Caso seja iterativo e apareçam somatórios, escreva-os.

    V[n] - vetor de inteiros
    A chamada do algortimos é:
       A (1, n, d)     e   B(n, d)
   ************** A  ************************
   int A (int i,int n, int d)
   {
     int j, f1, item, cont, k, max, fim, pai;
     cont = 1;
     item = V[i];
     f1 = d*(i-1) + 2;
     pai = i;
     while ( (f1 <= n) && cont )
       {
         j = f1;
         max = V[f1];
         if ((f1 + d - 1) > n)
           {
             fim = n;
           }
         else
           {
             fim = f1 + d - 1;
           }
         for (k = f1+1; k<=fim; k++)
           {
             if (V[k] > max )
               {
                 j=k; max=V[k];
               }
           }
         if (item >= V[j])
           {
             cont = 0;
           }
         else
           {
             V[ pai ] = V[j];
             pai = j;
             f1 = d*(pai-1) + 2;
           }
       }
     V[ pai ] = item;
     return(0);
   }
   ********** Alg B  ***************
   int B(int n, int d)
   {
     int stat;
     int i, pai;
     pai = ((int)((n-2)/d)) + 1;
     for (i= pai; i>=1; i--)
       {
         stat = A(i,n,d);
       }
     return(0);
   }
   

   ************** A1  ************************
   Chamada:  A1 (n,k)
   void A1 (int n, int k)
   {
     int i,f,m;
     i = 0;
     f = (int)(log(n)/2);
     while ( 1 )
       {
          m = (int)((i+f)/2);
          p = 2**m;
          if (k < p){
               if (k >= (p/2) )
                 {
                   return(p/2);
                 }
               f = m;
            }
          else {
               if (k < 2*p)
                 {
                   return(p);
                 }
               i = m;
            }
       }
   }
   

   ************** A2  ************************
   Chamada:  A2 (1,n,k)
   int A2 (int i, int f, int k)
   {
     int a,b,p;
     if (i < f)
       {
          a = (int)log(i);
          b = (int)log(f);
          h = (int)((a+b)/2);
          p = 2**h;
          if (k < p)
            {
               if (k >= (p/2) )
                 {
                    return(p/2);
                 }
               else
                 {
                    return(A2(i, p/2, k));
                 }
            }
          else
            {
               if (k < 2*p)
                 {
                    return(p);
                 }
               else
                 {
                    return(A2(2*p, f, k));
                 }
            }
       }
   }
   

   ************** A3  ************************
   Chamada:  A3 (1, n)
   void A3 (int i, int f)
   {
     int j,continue;
     if (i <= f)
       {
          continue = 1;
          j = i;
          while ( (j <= f) && continue)
            {
               if (V[i] > V[j])
                 {
                    V[i] = V[j];
                    continue = 0;
                 }
               j = j + 1;
            }
          A3(i,(int)(f/2));
       }
   }
   ************** A4  ************************
   Chamada:  A4 (1, n)
   void A4 (int i, int f)
   {
     int j,continue;
     if (i <= f)
       {
          continue = 1;
          j = i;
          while ( (j <= f) && continue)
            {
               if (V[i] > V[j])
                 {
                    V[i] = V[j];
                    continue = 0;
                 }
               j = j + 1;
            }
          m = (int)((f-i)/5);
          A4(i,i+m);
          A4(i+m+1,i+2*m);
          A4(i+2*m+1,i+3*m);
       }
   }
   

3. Dê uma descrição precisa dos algoritmos de ordenação abaixo e analise suas respectivas complexidades de pior caso. A entrada é um conjunto de n inteiros.
   1. Ordenação por inserção(insertion sort)
   2. Ordenação por intercalação (merge sort)
   3. Ordenação por rápida (quick sort)
   
   
4. Dado um vetor V (ou tupla, i.e. elementos onde a ordem em que aparecem é relevante) de n elementos de Z, uma inversão ocorre quando $ i,j tais que i<j £ n e V[i] > V[j]. Diz-se que (i,j) é uma inversão de V.
   1. Escreva um algoritmo iterativo (não-recursivo) que calcule o número de inversões de V.
   2. Utilize divisão e conquista para obter um algoritmo recursivo. Dica: Este algoritmo deve ser semelhante ao MergeSort.
   3. Escreva sua relação de recorrência.
   4. Descreva as estruturas de dados e analise as respectivas complexidades dos algoritmos que você propôs acima.
   
   
5. Considere d sequências ordenadas de números inteiros. O número total de elementos é n. Descreva um algoritmo que obtenha uma única sequência ordenada com os n elementos em O(n log d).
   
   
6. Considere duas sequências ordenadas S e T, onde |S|=n, |T|=k e k<n. T é uma subsequência de S se todo elemento de T está em S. Proponha um algoritmo O(n) para determinar se T é ou não é uma subsequência de S.
   
   
7. Considere dois heaps h₁ e h₂ de tamanhos n e m, respectivamente. Escreva um algoritmo para construir um heap que contenha todos os elementos dos heaps h₁ e h₂. A complexidade do algoritmo deve ser O(log(m+n)) no pior caso.
   
   
8. Seja A[1,...,n] um vetor de números reais. Escreva algoritmos que executem qualquer sequência das duas operações a seguir:
   • Soma(i,y): soma o valor y ao i-ésimo número; e
   • SomaParcial(i): retorna a soma dos i primeiros números (å₁ⁱ A[i]);
   Observe que o número de elementos permanece fixo (não há inserções ou exclusões); a única mudança é em seus valores. Cada operação deve ser feita em O(log n) passos. Pode ser utilizado mais um vetor de tamanho n como área de trabalho.
   
   
9. Especifique uma estrutura de dados para armazenar um conjunto de elementos (composto de chave e valor). A estrutura deve prover as seguintes operações:
   • FindValue(x): Encontrar o valor associado com o elemento de chave x (retornar nil se x não pertence ao conjunto);
   • Insert(x,y):
   • Delete(x):
   • Add(x,y): soma o valor y ao valor corrente do elemento de chave x; e
   • AddAll(y): soma o valor y aos valores de todos os elementos do conjunto.
   A complexidade, no pior caso, deve ser O(log n) para cada uma dessas operações.
   
   
10. Seja x₁,x₂,...,x_n uma sequência de números reais (não necessariamente positivos). Escreva um algoritmo de complexidade O(n) para encontrar a subsequência x_i,x_i+1,...,x_j (de elementos consecutivos) tal que o produto x₁ * x₂ * ... * x_n seja máximo (dentre todas as subsequências de números consecutivos). O produto de uma subsequência vazia é definido como 1.
    
    
11. Suponha que você tenha uma algoritmo que funcione como uma caixa preta (você não pode ver como ele foi construído) e que tem as sequintes propriedades: se você insere qualquer sequência de números reais e um inteiro k, o algoritmo retorna "Sim" ou "Não", indicando se existe um subconjunto dos números reais cuja soma seja exatamente k. Mostre como usar esta caixa preta para encontrar o subconjunto cuja soma seja k. Você pode usar a "caixa preta" O(n) vezes (onde n é o tamanho da sequência de números reais).
    
    
12. Escreva um algoritmo de "busca binária" que não divida o conjunto de elementos em 2 subconjuntos de tamanhos (aproximadamente) iguais, mas sim em um subconjunto de tamanho um terço do original e outro de tamanho dois terços do original. Compare este algoritmo com o algoritmo de busca binária.
    
    
13. Escreva um algoritmo de "busca ternária" que primeiro testa se o elemento da posição n/3 é igual ao elemento procurado x e então, se necessário, testa o elemento da posição 2n/3 para verificar a igualdade com o elemento x e, possivelmente, reduzir o tamanho do conjunto para um terço do original.
    
    
14. Sejam x₁,x₂,...,x_n e y₁,y₂,...,y_n sequências de inteiros ordenadas de forma não decrescente. Escreva um algoritmo que encontre a mediana da intercalação dos 2n elementos. (Dica: use busca binária).
    
    
15. 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.
    • Determine a complexidade deste algoritmo; e
    • Qual é a complexidade se ad + bc é calculado como (a + b)(c + d) - ac - bd?
    
    
16. Prove que se k é uma constante não negativa e n é potência de 2, então T(n) = 3kn^{log₂ 3} - 2kn é a solução da recorrência:

    T(n) =

    ì í î

    k, n = 1 3T(n/2) + kn, n > 1

    
    
17. • A equação abaixo utiliza o fato de que a soma å_i=0^¥(i/2ⁱ) converge e é menor do que 2. Prove este fato.

      å 1 £ i £ k

      2i-1(k-i) =

      å 1 £ i £ k-1

      i2k-i-i £

      å 1 £ i £ k-1

      i/2i < 2n = O(n)

    • Use indução para mostrar que å_i=1^k 2^i-1(k-i) = 2^k - k - 1, k ³ 1.
    
    
18. Especifique um tipo abstrato de dados que suporte as seguintes operações:
    • Insere(x): cada elemento só pode ser inserido no máximo uma vez; e
    • Remove(y): remover qualquer elemento da estrutura de dados e armazená-lo em y.
    Considere que os elementos são identificados por números inteiros no intervalo de 1 a n e que n é pequeno o suficiente para permitir a alocação de memória de tamanho O(n). Escreva algoritmos de complexidade O(1) para as operações acima.
    
    
19. Sejam os conjuntos S=(x₁ ,...,x_n ) e T=(y₁ ,..., y_r ). Considere 1 £ x_i £ m para 1 £ i £ n e 1 £ y_i £ m para 1 £ i £ r. Considere também que todos os elementos de S e T são inteiros. Escreva um algoritmo de complexidade O(n+r) para determinar se o conjunto S está contido em T. Qual a quantidade de espaço que será usada pelo algoritmo? Sabendo que S é igual a T se e somente se S esta contido em T e T está contido em S, demonstre que determinar se os dois conjuntos são iguais tem complexidade linear.

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