ALGORITMOS E ESTRUTURAS DE DADOS II

                       Primeira lista de exercicios

1) Conceitue:
   a) algoritmo    b) tipo de dados  c) tipo abstrato de dados

2) Avalie os seguintes somatorios:

  a) somatorio de i para i variando de 5 a n

  b) somatorio de a^i para i variando de 1 a n

  c) somatorio de 2^(k-i) para i variando de 0 a k

  d) somatorio de 2^(i-k) * i^2 para k variando de 0 a i

3) Resolva as seguintes equacoes de recorrencia:

  a) T(n) = T(n-1) + c, c constante, n>1; T(1) = 0

  b) T(n) = T(n-1) + n - 1; T(1) = 0

  c) T(n) = 2T(n/2) + n - 1; T(1) = 0

  d) T(n) = T(n/2) + 1 ; T(1) = 1

  e) T(n) = 2T(n/2) + 1 ; T(1) = 1

  f) T(n) = T(n-1) + 2^n; T(0) = 1

4) Suponha dois algoritmos A e B com funcoes de complexidade de tempo dadas
   por a(n) = n^2 - n + 549 e b(n) = 49n + 49 respectivamente. Determine
   quais valores de n no conjunto dos numeros naturais para os quais A leva
   menos tempo para executar que B.

5) Considere o algoritmo a seguir. Suponha que a operacao crucial e' o fato
   de inspecionar um elemento. Neste caso o algoritmo inspeciona os n
   elementos, o que de alguma forma lhe permite descartar 1/3 deles;
   entao ele faz uma chamada recursiva sobre os 2/3 restantes.

   Pesquisa(n)
   if n<=1
   then "inspecione elemento" e termine
   else begin
      para cada um dos n elementos "inspecione elemento"
      Pesquisa( 2n/3 );
   end;

   a) Escreva a relacao de recorrencia que descreva este comportamento
   
   b) Converta essa relacao para um somatorio

   c) Determine a forma fechada do somatorio

6) Determine o pior caso dos seguintes procedimentos em funcao de n:

           procedure multmat(n:integer);
           var i,j,k:integer;
           begin
              for i:=1 to n do 
                 for j:=1 to n do begin
                    C[i,j] := 0;
                    for k:=1 to n do
                       C[i,j] := C[i,j] + A[i,k] * B[k,j];
                 end;
           end;

           procecure misterio(n:integer);
           var i,j,k,l: integer;
           begin
              for i:=1 to n-1 do
              for j:=i+1 to n do begin
                 for k:=1 to j do
                    { Alguma operacao de complexidade O(1) }
                 for k:=1 to sqrt(n) do
                    { Alguma operacao de complexidade O(1) }
              end;
           end;

           function recursiva(n:integer);
           begin
              if n<=1 then
                 recursiva := 1;
              else
                 recursiva := recursiva(n-1) + recursiva(n-1);
           end;

   OBS.: Para o procedimento misterio, considere dois casos para a
         complexidade da funcao sqrt(x) (parte inteira da raiz quadrada):

        O(sqrt(x)) = O(x^(0.5)) - sqrt tem complexidade igual `a raiz quadrada
        O(sqrt(x)) = O(1)       - sqrt tem complexidade constante

7) Ordene as seguintes funcoes em termos da taxa de crescimento (complexidade)
   n, sqrt(n), log(n), log(log(n)), log(n)^2, n/log(n), sqrt(n)log(n)^2,
   (1/3)^n, (3/2)^n, 17. 

8) Considere o seguinte algoritmo (conhecido como "regra de Horner") para
   se calcular o valor de um polinomio de grau n dado por
             p(x) = somatorio de i=0 a n de (a[i].x^i),
   onde a[0..n] contem os coeficientes de cada termo do polinomio:

                 function polinomio( n:integer;
                                     x:integer,
		                     a:array[0..max] of integer
		                   ): integer;
                 var p: integer;
                 begin
                    p := 0;
                    for i:=n downto 0 do
                       p := x * p + a[i];
                    polinomio := p;
                 end;

   a) Mostre os passos do processamento desse algoritmo para
      x=3, p(x) = 4 x^4 + 8 x^3 + x + 2.
   
   b) Explique porque este algoritmo funciona.

   c) Qual a complexidade do algoritmo (em funcao do grau do polinomio, n)?

9) Dois programas A e B foram analisados e os respectivos limites de pior
   caso foram determinados como sendo 150n*log(n) e n^2. Se possivel,
   responda `as seguintes perguntas:

   a) Qual dos programas tem melhor garantia de desempenho para valores
      grandes de n (n>10000)?

   b) Qual dos programas tem melhor garantia de desempenho para valores
      pequenos de n (n<100)?

   c) Qual programa executara' mais rapido na media para n=1000?

   d) E' possivel ao programa B executar mais rapido que A para todas
      as entradas possiveis?