Sujeito a mudanças...
Março
Leitura recomendada: Knuth, vol 1, pg 238-243.
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: Resolva o exercício 1 acima com uma fila dupla no lugar da pilha.
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.
Dificuldades com backtrack? Leia a seção 3.4 do Wirth, pg 120-129, onde ele tenta dar uma receita para se projetar algoritmos de tentativa e erro.