Sujeito a mudanças...
Fevereiro
Exercício 1: Suponha que inserimos e
removemos os elementos 1,2,...,n de uma pilha em alguma ordem onde
as inserções vêm na ordem 1,2,...,n (mas eventualmente
intercaladas com as remoções). Caracterize as permutações de 1 a
n que podem ser obtidas como ordem de saída da pilha. (Ou seja,
determine uma condição necessária e suficiente que uma permutação
tem que ter para que possa ser obtida como saída.)
Exemplo: A permutação 2,1,3 pode ser obtida, enquanto que a
permutação 3,1,2 não.
Exercício 2: Dê o protótipo das sete operações que manipulam uma fila dupla com uma descrição de uma linha do que cada operação faz, como feito em aula para filas e pilhas.
Exercício 3: Resolva o exercício 1 acima com uma fila dupla no lugar da pilha.
Desafio: Suponha que um procedimento
manipula um vetor v com N posições inicializadas anteriormente com
0. Esse procedimento consome tempo O(n) (e portanto, em particular,
acessa O(n) posições do vetor v). Então a inicialização do vetor,
feita da maneira natural, e o procedimento consomem, juntos, tempo
O(N), supondo que N seja maior que n. Em situações em que N é
muuuuito maior do que n, é desejável encontrar uma maneira
alternativa de manipular o vetor que não exija a inicialização
completa do vetor, afinal várias de suas posições nem sequer serão
acessadas pelo procedimento. Bole uma maneira de modificar o
procedimento (ou seja, os acessos que este faz às posições do
vetor) de maneira a evitar que o vetor precise ser previamente
inicializado. A sua modificação do procedimento deve consumir
tempo O(n) para fazer o processamento correspondente ao
procedimento original no vetor.
Você
pode usar mais espaço para fazer isso...
Leitura recomendada: seção 2.2.1 do volume 1 da coleção do Knuth (The Art of Computer Programming).
Veja o arquivo desenho.ps com o exemplo
visto em aula levemente alterado. Para visualizar um arquivo .ps
você pode usar o programa gv do unix/linux (ou ghostview para
windows). Para ver o arquivo fonte o arquivo fonte (e não o
desenho produzido) ou alterá-lo, use um editor de arquivos texto
qualquer, como por exemplo o que você usa para editar seus
programas em C.
Quer aprender mais sobre postscript?
Visite aqui
a página do Luc Devroy sobre isso.
Exercício 1: Escreva um arquivo texto desenho1.gz em postscript com o desenho de uma estrela de 6 pontas, usando a função hill vista em aula e presente no arquivo acima.
Exercício 2: Escreva um arquivo texto desenho2.gz em postscript com o desenho de uma estrela de 5 pontas, como pedido em aula.
Desafio: No pior caso, quanto espaço (em notação assintótica) da pilha de execução pode consumir a implementação usual do quicksort para ordenar um vetor de tamanho n? Como implementar o quicksort de modo a gastar (assintoticamente) menos que isso?
Leitura recomendada: seção 4.3 do livro do Sedgewick, Algorithms in C, Parts 1-4.
Exercício: Considere o seguinte problema:
SUBSETSUM: Dado um número S e uma seqüência de n números, determinar todas as subseqüências da seqüência dada cuja soma é exatamente S.Resolva o problema acima por força bruta usando o algoritmo de geração de subseqüências visto em aula.
Exercício 1: Escreva um algoritmo que, dado
o apontador para uma lista ligada simples, inverte essa lista.
Exercício 2: Escreva um algoritmo que, dado
n e k, calcula o lider escolhido pela eleição de Josephus dos
elementos de 1 a n, com parâmetro k.
Exercício 3: Escreva um algoritmo que, dado
n, imprime todos os números primos entre 1 e n. Use o crivô de
Eratósthenes.
Leitura recomendada: seções 3.3 a 3.5 do livro do Sedgewick, Algorithms in C, Parts 1-4.
Planaridade em grafos: ficou curioso a esse respeito? Gostaria de saber um pouco mais sobre algoritmos que decidem se um grafo é ou não planar? Dê uma olhada na dissertação de mestrado [ps.gz] do Alexandre Noma, um ex-aluno do BCC, onde é apresentado um dos algoritmos lineares de planaridade em detalhes e é feito um estudo experimental de alguns algoritmos de planaridade. No capítulo 3, aparece a descrição de um algoritmo mais simples, que pode ser implementado sem tanto esforço em tempo quadrático. No capítulo 4 começa a descrição da implementação linear, e em particular o uso das listas duplamente ligadas diferentes, etc (na implementação das PC-árvores lá descritas).