PRIMEIRA PROVA DE ESTRUTURAS DE DADOS BCC, 1O. SEMESTRE DE 2008

Instruções:

1. Não destaque as folhas do caderno de soluções.

2. A prova pode ser feita a lápis. Cuidado com a legibilidade.

3. Não é permitido o uso de folhas avulsas para rascunho.

4. Não é necessário apagar rascunhos no caderno de soluções.

5. Asserções imprecisas valem pouco. Justifique suas asserções (dentro do razoável!).

1. [3 pontos] Seja dado um inteiro positivo N. Queremos gerar N inteiros x_{1}, …, x_{N} em S = {0, 1, …, N^{2} − 1}, sem repetição, com todos os inteiros em S equiprováveis. Descreva um algoritmo para fazer isso. Seu algoritmo pode usar espaço O(N) e deve ter complexidade de tempo não muito maior que O(N), isto é, ele deve demorar tempo não muito maior que O(N) (se você conseguir um algoritmo que, tipicamente, roda em tempo O(N log N), já está bom). Diga explicitamente quais são suas hipóteses e justifique suas afirmações ao descrever sua solução.

Você deve supor que você tem acesso a um gerador de números aleatórios RAND(), que devolve um inteiro em S, com todos esses inteiros equiprováveis.

2. [3 pontos] Sejam dadas duas matrizes A = (a_{ij}) e C = (c_{ij}) de inteiros, ambas m × n, satisfazendo a_{ij} ≤ c_{ij} para todo i e j. Uma solução para o problema P (A, C) é uma matriz de inteiros B = (b_{ij}) com a_{ij} ≤ b_{ij} ≤ c_{ij} para todo i e j, com a propriedade de que (a) em toda linha de B um mesmo inteiro não ocorre mais de uma vez, e (b) em toda coluna de B um mesmo inteiro não ocorre mais de uma vez.

(i) Considere as matrizes

A = (\begin{matrix}1 & 2 & 2 \\ 3 & 3 & 4 \end{matrix}) ,  C = (\begin{matrix}2 & 3 & 3 \\ 4 & 5 & 5 \end{matrix}) .  (1)

Encontre uma solução para o problema P (A, C) para as matrizes A e C acima. (ii) Exiba explicitamente uma matriz M para o Problema da Cobertura Generalizada (PCG)

com a propriedade de que as soluções do PCG para M correspondem às soluções do P (A, C), onde A e C são as matrizes dadas em (1).

(iii) Resolva (ii) para matrizes A e C genéricas. (Naturalmente, você deve descrever M de

alguma forma sistemática, em função dos a_{ij} e c_{ij}.)

3. [4 pontos] Seja B_{N} uma ABB obtida da seguinte forma: sorteamos uma permutação das chaves 1, …, N, com todas as N! permutações equiprováveis. Inserimos essas chaves em uma ABB inicialmente vazia, na ordem dada pela permutação sorteada. Seja B_{N} a ABB (aleatória) assim obtida.

(i) Desenhe todas as ABBs com N = 4 nós (são 14), supondo que temos as chaves A, B, C e D. Diga qual é a probabilidade de obtermos cada uma delas como uma B_{N} (naturalmente, com N = 4).

(ii) Considere agora o algoritmo de inserção aleatorizado, visto em sala (Programa 13.2 de

Sedgewick), reproduzido abaixo:

        link insertT(link h, Item item)
          { Key v = key(item);
            if (h == z) return NEW(item, z, z, 1);
            if (less(v, key(h->item))) { h->l = insertT(h->l, item); h = rotR(h); }
                                  else { h->r = insertT(h->r, item); h = rotL(h); }
            return h;
          }
        link insertR(link h, Item item)
          { Key v = key(item), t = key(h->item);
            if (h == z) return NEW(item, z, z, 1);
            if (rand()< RAND_MAX/(h->N+1)) return insertT(h, item);
            if less(v, t) h->l = insertR(h->l, item);
                     else h->r = insertR(h->r, item);
            (h->N)++; return h;
          }
        void STinsert(Item item)
          { head = insertR(head, item); }

Considere a ABB

                    C
                   / \
                  B   D
                 /
                A

Suponha que inserimos as chaves A, B, C, e D em uma ABB inicialmente vazia, usando o algoritmo de inserção aleatorizado dado acima. Diga qual é a probabilidade de obtermos a ABB acima, quando executamos as inserções nas três ordens abaixo:

(a) A, B, C, D,

(b) D, C, B, A,

(c) B, D, A, C. Para determinar as probabilidades pedidas acima, você deve fazer as contas explicitamente, analisando o algoritmo passo a passo.