MAC338  PROVA 3  4/7/2000

Duração da prova: 2 horas

1. [3 pontos] (i) Prove que n^{α} = O(n^{β}) se e só se α ≤ β. (ii) Determine uma condição necessária e suficiente para os pares (α_{1}, α_{2}) e (β_{1}, β_{2}) para que tenhamos

n^{α_{1}}(log n)^{α_{2}} = O ((n^{β_{1}}(log n)^{β_{2}})). (iii) Sabe-se que o k-ésimo primo p_{k} é tal que p_{k} = Θ(k log k). Seja π(n) o número de números primos p

com 1 < p ≤ n. Deduza que π(n) = Θ(n/ log n).

2. [3 pontos] O Problema da Seleção s(n, k, x) tem como entrada inteiros 1 ≤ k ≤ n e uma seqüência de inteiros x = (x_{1}, …, x_{n}). Neste problema, queremos encontrar um x tal que

|{i: x_{i} ≤ x}| ≥ k e |{i: x_{i} ≥ x}| ≥ n − k + 1.

Por exemplo, o problema s(n, 1, x) consiste na determinação do menor elemento em x e o problema s(n, ⌊n/2⌋, x) consiste na determinação da mediana dos elementos em x.

(i) Descreva um algoritmo para resolver s(n, k, x). O seu algoritmo deve ter complexidade de pior caso O(n log n).

(ii) Suponha agora que os inteiros que ocorrem em x são todos distintos e que formam um conjunto (desconhecido) X. Suponha que queremos resolver s(n, k, x), onde x é uma dentre todas as n! possíveis permutações de X, com todas estas permutações equiprováveis. Descreva um algoritmo para resolver s(n, k, x) nestas condições que tem complexidade de caso médio O(n).

(iii) Argumente que o seu algoritmo em (ii) de fato tem complexidade de caso médio O(n). Para sua resposta estar completa, você precisa fazer uma análise quantitativa de seu algoritmo.

3. [3 pontos] Nesta questão, estamos interessados em grafos orientados G. Suponha que represetamos nossos grafos por matrizes de adjacência A(G) = (a_{ij}), onde colocamos a_{ij} = 1 se o arco (i, j) está presente em G e a_{ij} = 0 caso contrário. Considere agora o seguinte trecho de código:

    for (y = 0; y < n; y++)
      for (x = 0; x < n; x++)
        if (a[x][y])
          for (j = 0; j < n; j++)
            if (a[y][j]) a[x][j] = 1;

(Os vértices de G são 0, …, n − 1.)

(i) Dê um limitante superior para o número de vezes que a atribuição a[x][j]=1; é executada. (ii) Descreva o efeito do trecho de código acima (para tanto, você poderia considerar o grafo que a nova

matriz representa.)

4. [3 pontos] Considere a função abaixo, que é utilizada na manipulação de heaps.

    void fixDown(Item a[], int k, int N)
      { int j;
        while (2*k <= N)
          { j = 2*k;
            if (j < N && less(a[j], a[j+1])) j++;
            if (!less(a[k], a[j])) break;
            exch(a[k], a[j]); k = j;
          }
      }

(i) Em que situação usamos fixDown()? Descreva cuidadosamente as hipóteses sobre o heap no momento em que chamamos esta função e explicite qual é o efeito da execução de fixDown().

(ii) O que se entende pela altura de um elemento em uma árvore? Não deixe de dar um exemplo

ilustrativo. Lembre-se de que folhas têm altura 0. (iii) Dê um limitante superior para o número de vezes que executamos exch() em função da altura do

elemento apontado por k no momento da chamada de fixDown(). (iv) Relacione o tempo de construção de um heap a partir de um vetor arbitrário com n elementos com

a soma das alturas dos nós da árvore binária completa com n nós.

(v) Seja f(n) a soma das alturas dos nós da árvore binária completa com n nós. Mostre que f(n) satisfaz a recorrência f(1) = 0 e f(n) = f(⌊n/2⌋) + ⌊n/2⌋ para n ≥ 2.

(vi) Mostre que f(n) = n − b(n), onde b(n) é o número de bits 1 na expansão binária de n. Deduza que podemos construir um heap a partir de um vetor arbitrário com n elementos executando no máximo n trocas de elementos do vetor (execuções de exch()).