Lista B

Vimos na aula:
Algoritmo CGM para o problema de seleção: dados n números e um inteiro k entre 1 a n, achar o k-ésimo menor número. Técnica de reduzir a entrada de tamanho n para n/p para depois resolver o problema sequencialmente num processador. Os slides usados nesta aula (.pdf 108K). Mais detalhes no artigo Saukas e Song 1998 (html).

O algoritmo CGM de Saukas e Song para seleção necessita de O(log p) rodadas de comunicação.

Usando a idéia de p-separadores (como foi visto no algoritmo split sort), projete um algoritmo CGM de seleção que usa apenas O(1) rodadas de comunicação. Uma solução óbvia é ordenar tudo e depois seleciona, mas dá para fazer de forma mais simples.

Last modified: Tue Apr 20 16:27:35 EST 2004