PRIMEIRA PROVA DE PRINCÍPIOS DE DESENVOLVIMENTO DE

ALGORITMOS BE/BM/BMA, 2O. SEMESTRE DE 2006

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!).

6. IMPORTANTE: Faça no máximo 3 questões.

1. [2 pontos] Diga se são verdadeiras ou falsas as seguintes fórmulas:

(i) 5n(n − 1)(n − 2) = 5n^{3} + O(n^{2}) (ii) 5n(n − 1)(n − 2) = O(n^{3}) (iii) 2^{f(n)} = O(2^{n^{3}}), onde f(n) = 5n(n − 1)(n − 2) é como em (ii) (iv) H_{n} = 1 + 1/2 + 1/3 + ⋯ + 1/n = ∑_{1≤k≤n} 1/k = O(log n) Justifique suas respostas.

2. [3 pontos] Considere o problema da conexidade, estudado no começo do semestre: são dados pares p_{1}, …, p_{M} com p_{i} = (x_{i}, y_{i}) e 0 ≤ x_{i}, y_{i} < N para todo i. Queremos ‘filtrar’ esta seqüência de pares de forma que apenas aqueles pares ‘essenciais’ sejam impressos (o par p_{i} deve ser impresso se e só se x_{i} e y_{i} pertencem a diferentes componentes conexas definidas pelos pares p_{j} (j < i)).

(i) Suponha que a entrada é

(1, 4), (1, 9), (2, 5), (6, 9), (0, 8), (3, 7), (1, 8), (2, 0),
(3, 5), (3, 8), (5, 9), (6, 0), (6, 7), (2, 4), (4, 7).

Qual é a saída correspondente? Não dê apenas a saída; mostre como você chegou a ela (basta fazer uns diagramas e explicar o que está “acontecendo”).

(ii) Descreva cuidadosamente uma solução para este problema. (Lembre-se de que vimos várias estruturas de dados e algoritmos em sala.) Não deixe de exemplificar como a solução que você descreve funciona no exemplo em (i).

(iii) O que ocorre se reordenarmos os pares na entrada dada em (i)? Mais precisamente, a saída será necessariamente diferente? Poderá ser diferente? O número de pares na saída é o mesmo para qualquer ordenação dos pares em (i)? Você consegue encontrar duas ordenações dos pares em (i) de forma que as saídas sejam disjuntas (um mesmo par não aparece em ambas as saídas)? Por quê?

3. [3 pontos] Escreva um algoritmo, baseado no uso de pilha, para resolver o seguinte problema. Dada uma frase, a saída do algoritmo deve ser a mesma seqüência de palavras, mas com suas letras em ordem inversa.

Por exemplo, com a entrada ESTE EXERCICIO E MUITO FACIL, seu algoritmo deve ter como saída ETSE OICICREXE E OTIUM LICAF. Se você quiser, você pode supor que a frase de entrada contém apenas letras maiúsculas e brancos, e que o último caracter é um branco.

Escreva sua solução na forma de pseudocódigo (isto é, não é necessário escrever em C). A estrutura geral de sua solução deve ser como segue

Algoritmo Inverta Palavras(s)

1….

2. enquanto há caracteres para ler

3. c = próximo caracter de s 4….

4. [4 pontos] Nesta e na próxima questão, você deve escrever código em C. Ademais, supomos

que temos

  typedef struct node *link;
  struct node { int item; link next; };

Escreva uma função de protótipo

  link elimine(link h, int x);

que recebe como entrada um ponteiro para a cabeça de lista heada de uma lista ligada e que devolve a mesma lista sem as células com item x. A função deve devolver um ponteiro para heada; a memória ocupada pelas células eliminadas da lista (aquelas com item x) deve ser liberada. Você deve supor que as listas não têm cauda (em particular, se a lista dada está

vazia, temos h->next == NULL).

O que ocorreria se tivéssemos listas ligadas sem cabeça nesta questão?

5. [2 pontos] Escreva uma função de protótipo

  link remova(link a, link b);

que recebe como entrada ponteiros para as cabeças de lista heada e headb de duas listas ligadas e que remove da lista a as células com itens que ocorrem na lista b. A função deve devolver um ponteiro para heada; sua função deve manter a ordem relativa das células que não foram eliminadas e deve manter a lista b intacta.

Por exemplo, se a lista a tem 10 células, com itens 3, 1, 4, 1, 5, 9, 2, 5, 3, 5 respectivamente e b tem 3 células, com itens 2, 7, 1 respectivamente, então a saída deve ter 7 células, com itens 3, 4, 5, 9, 5, 3, 5.

Use a função elimine() da questão anterior, mesmo que você não a tenha feito.