Tópicos abordados na aula.
-
Segunda aula (4, 5 de Março):
Apresentação de algoritmos Union&Find
Objetivos: Recordar o raciocínio necessário a elaboração de algoritmos
Noções de análise de complexidade
Problema: Dados N inteiros (O a N-1) e uma sequência de pares de
inteiros representando uniões transitivas imprimir apenas os pares que
representem novas uniões. Os pares de inteiros são terminados pelo par
(0,0).
Encontre aqui:
- Uma implementação para gcc (linux):
unionfind.c (também foi implementada uma adaptação
do QuickUnion que apenas diminui os caminhos).
- Testes de tempo para 1000, 10000 e 50000 elementos.
- Testes dos algoritmos rápidos para 100000 e 500000 elementos.