Trabalho Pratico 02 - Investigando Algoritmos de Ordenação e Busca

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Trabalho Prático 02
Investigando Algoritmos de Ordenação e Busca
Objetivo: Exercitar a análise e a aplicabilidade de algoritmos de ordenação e de busca.
Modalidade de desenvolvimento: equipe (até 2 componentes)
Modalidade da apresentação: envio no formato .odt1 para flaviacoelho@ufersa.edu.br
Data de entrega: Domingo, 02/10/2016
Artefatos de entrega: soluções das questões, a seguir.
Atenção: Nas justificativas, apresente todos os cálculos matemáticos relacionados.
1. (0,5 pt) Modifique o algoritmo de ordenação por inserção de forma que ele utilize a busca
binária para encontrar a posição de inserção de um elemento no vetor destino. Determine a
complexidade computacional do algoritmo obtido e apresente a sua implementação.
2. (1 pt) Alice e Bob precisam ordenar uma coleção de n porcas e n parafusos, por tamanho.
Assume-se que para cada parafuso, há uma porca correspondente do mesmo padrão, mas
inicialmente não se sabe qual é a correspondência correta. Considere que é possível apenas
comparar os tamanhos de uma porca e um parafuso tentando encaixá-los um no outro
(assuma que essa comparação ocorre em tempo constante). Tal operação apenas indica se a
porca é maior que o parafuso, que o parafuso é maior que a porca ou que são do mesmo
tamanho. Qual é a complexidade computacional de ordenar as porcas e parafusos no pior
caso? Justifique.
3. (1 pt) Elabore um algoritmo eficiente (em tempo O(K)) para encontrar, dada uma chave K e
uma árvore heap, todos os nodos com chaves menores que K.
4. (0,5 pt) Bob propõe que Alice advinhe um número inteiro entre 0 e N. Bob permite que ela
faça perguntas apenas na forma “o número é menor que 100?”, por exemplo, às quais ele
responde “Sim” ou “Não”. Prove que Alice precisa fazer não mais que lgN perguntas e
descobrir o número.
1 De acordo com o modelo disponíve via SIGAA.
1
	Trabalho Prático 02