Lista de exercicio 7 Analise e Projeto de Algoritmos

Aluno: Vinícius Barcelos Silva
Matricula: 108251
Lista 7 7.1­2
Quando todos os elementos de A são iguais, devemos nos atentar ao fato de que a comparação na linha 4 do PARTITION será sempre aceita, sendo assim i será incrementado sempre e desde que tenhamos inicialmente i = p­1 e i+1, será retornado o valor r­1.
Para fazermos com que seja q = (p+r)/2 quando todos os elementos são iguais, devemos modificar o algoritmo de forma a tratar esse caso através da contagem do número de comparações em que A[j] =
A[r] e depois subtrair metade desse número a do índice do pivô. 7.1­4
Apenas mudando a condição da linha 4 do PARTITION de “<=” para “>=”. 7.3­1
Pelo fato de que o pior caso é gerado a partir de uma saída específica que é gerada de forma aleatória, o que a torna rara. Logo não se tem interessados em analisar o seu desempenho pelo fato de não podermos reproduzi­lo de forma confiável. 7.1 a,b e c)Os índices não andarão pela matriz. Na primeira verificação i <j, i = p e j≥p (porque um [p] = x). Se i
= j, o algoritmo irá terminar sem acessar elementos "inválidos". Se i <j, o próximo ciclo também terá índices i e j dentro da matriz, (porque i≤r e j≥p). Note­se que se um dos índices chega ao fim da matriz, então i não será inferior ou igual a j mais. Como para o valor de retorno, será pelo menos um a menos que j. Na primeira iteração, ou (1) A[p] é o elemento máximo e depois i = p e j = p <r ou (2) A [p] não é trocada por A[j] onde j≤ r. O laço não será encerrado e na próxima iteração, j fica diminui até que os valores obtidos de volta.Combinando esses dois casos temos p≤j <r. d)
Inicialização: Temos dois blocos de repetição para estabelecer apenas esta condição. Manutenção: Através da troca de A[i] e A[j] fazemos a A [p..i] ≤x e A [j..r] ≥x. Incrementando i e decrementando j para manter este invariante. Término: O ciclo termina quando i≥j. A invariante ainda detém na rescisão. O terceiro bit segue diretamente a