Esta lista é individual. Em caso de cópia será atribuída a nota 0 (zero) a todas as listas idênticas.
Todas as implementações devem ser feitas em C, o executável disponibilizado em disquete, devidamente documentado, que possa ser executado pelos monitores, e devem ter uma interface que permita o teste da solução.
A solução de cada questão deve ser entregue junto com o código fonte, tudo devidamente organizado e comentado.
Cada dia de atraso implica em 0,5 ponto a menos na nota desta lista.
Esta lista contem 4 questões.
A entrada e' "d" sequencias de elementos tal que cada sequencia ja'
esta' ordenada, e ha' um total de n elementos.Implemente um algoritmo
que mescle(faca a uniao de) todas as sequencias em uma unica sequencia
ordenada em O(n*log d)..
(2,5)
Dado dois conjuntos S1 e S2, e um numero real x,descubra se existe um
elemento de S1 e um elemento de S2 cuja soma e' exatamente x.Seu
algoritmo deve rodar num tempo de O(nlogn), onde n e' o numero total de
elementos em ambos os conjuntos. (2,5)
Implementar a versao mediana de tres do quicksort. Nessa versao, definimos
o pivot como sendo o valor do "meio" entre o primeiro elemento, o ultimo e
o localizado na metade do conjunto a ser ordenado.
(2,5)
A entrada e' uma sequencia x1,x2,....,xn de inteiros numa ordem
arbitra'ria , e uma outra sequencia a1,a2,....,an de inteiros distintos
de 1 ate' n(ou seja, a1,a2...,an e' uma permutacao de 1,2,...,n). Ambas
as sequencias sao dadas como arrays. Implemente um algoritmo de ordem
O(nlogn) para ordenar imposto ( de acordo com a) pela permutacao. Em
outras palavras , para cada "i", xi deve aparecer na posicao dada em ai.
Por exemplo,se x = 17,6,2,9, e a = 3,2,4,1, entao a saida deve ser
x = 9,6,17,2.O algoritmo deve ser `in place`, entao voce nao pode usar um
array adicional.
(2,5)