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 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)