MAC0338  Análise de Algoritmos

Tarefa 9

Entregue os exercícios abaixo até a quarta-feira, dia 19 de maio.

EXERCÍCIO 1 [CLR 9.1-1, CLRS 8.1-1]
Qual o menor profundidade (= menor nível) de uma folha em uma árvore de decisão que descreve um algoritmo de ordenação baseado em comparações?

EXERCÍCIO 2 [CLRS 9.1-1]
Mostre que o segundo maior elemento de um vetor A[1..n] pode ser encontrado com não mais que

n + teto(log n) - 2
comparações.

EXERCÍCIO 3 [CLRS 7.7-4]
O QUICKSORT contém duas chamads recursivas. A segunda chamada recursiva não é realmente necessária. Considere a seguinte versão do QUICKSORT 

QUICKSORT2 (A,p.r) 
   1. enquanto p < r faça
   2.    q <- PARTICIONE(A,p,r)
   3.    QUICKSORT2(A,p,q-1)
   4.    p <- q + 1
Compiladores usualmente geram código que executa procedimentos recursivos através de uma pilha que contém, entre outras coisas, endereço de retorno da chamada e parâmetros. A cada chamada recursiva as infomações da chamada são colocadas no topo da pilha. Quando a execuçao da função é encerrada, as informações referentes à sua chamada são removidas da pilha. Suponha que as informações de um vetor são colocadas na pilha através de um ponteiro. Assim, a cada chamada do QUICKSORT ou do QUICKSORT2 a quantidade de informação que é colocada na pilha é O(1). Considere a execução do QUICKSORT2 para ordenar n elementos.
  1. Descreva um situação em que a altura da pilha de execução do QUICKSORT2 é theta(n).
  2. Modifique o QUICKSORT2 para que, no pior caso, a altura da pilha de execução seja theta(lg n).

Last modified: Wed May 19 12:21:04 BRT 2004