MAC 122 Princípios de Desenvolvimento de Algoritmos Terceira lista de exercícios (turma do básico) Entregar na aula de 19out99. Prazo improrrogável. Equipes de <= 2 alunos. 1. Escreva uma versão do Heapsort que conta o número de comparações efetuadas ao ordenar uma dada entrada. Sugere-se usar o seu programa nas duas questões seguintes. 2. (9.32) Para N=32 encontre uma permutação de chaves que força Heapsort a executar o maior número possível de comparações. Quantas comparações são feitas? Justifique que encontrou o pior caso. 3. (9.33 parcial) Uma permutação é tão mais econômica quanto menos comparações o Heapsort do livro executar para ordená-la. Encontre a permutação mais econômica que conseguir para N=32. Quantas comparações são feitas? Explique como encontrou a permutação. 4. Escreva um programa que calcula o valor de uma expressão infixa totalmente parentetizada. Sugere-se aplicar, em sequência, os dois clientes de pilhas vistos em aula. Processe vários exemplos.MAC 122 Princípios de Desenvolvimento de Algoritmos
e-mail:
Imre Simon <is@ime.usp.br>
Last modified: Wed Oct 6 19:08:29 EDT 1999