✓: recebido. ✓✓ : avaliado.

Entrega: 3 de março 2024.

• Implementar um heap k-ário.
• Implementar o algoritmo de Dijkstra usando o heap implementado.
• Determinar o valor de k tal que o algoritmo de Dijkstra com um heap k-ário tem o melhor desempenho.
• Comparar a complexidade teórica pessimista com a complexidade real. Em particular verificar que a complexidade real respeita o limite teórico.
• Avaliar o escalonamento do algoritmo Dijkstra.

• Verificação da complexidade do Dijkstra: usar o gerador de casos de testes abaixo.
• Verificação do escalonamento: o caso de teste é o rede de trânsito de New York e dos EUA (distance), que pode ser baixado na página do DIMACS challenge.
• Para testar em geral: Gerar um número suficiente (>30) de pares aleatórias de vértices origem e destino e medir o tempo de execução e o número de operações “insert”, “deletemin” e “decreasekey”.
• Exemplo de um plano de teste.

• Como o grafo possui 23,947,347 vértices é necessário usar uma representação esparsa. Uma matriz de adjacência, em particular, não serve.

• As implementações do algoritmo de Dijkstra devem aceitar um grafo no formato da DIMACS challenge na entrada padrão (stdin), os índices de dois vértices origem e destino na linha de comando e imprimir o valor do caminho mais curto na saída padrão (stdout). Caso não existo caminho entre os dois vértices imprimir “inf”. Exemplo (em UNIX)

> ./dijkstra 1 2 < NY.gr
803

• Um relatorio explicando a) possíveis detalhes relevantes da implementação, b) o ambiente de teste, c) o resultado dos experimentos, e d) uma análise
• O código fonte da implementação
• Arquivos csv com todos dados experimentais

• Repositório com alguns códigos de suporte.

Entrega: 10 de julho de 2024.

• Implementar o algoritmo de Edmonds-Karp para encontrar o fluxo máximo s-t.
• Verificar a complexidade do algoritmo experimentalmente.

• Um gerador de casos de teste em formato DIMACS em C é disponível aqui.
• Exemplo de um plano de teste.

• As implementações do algoritmo devem aceitar uma instância no formato DIMACS na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).

• O código maxflow.cpp calcula o fluxo máximo. Para compilar: Usar C++ e Boost.

Entrega: 23/07/2024

• Implementar o algoritmo de Hopcroft-Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos.
• Documentar a implementação, em particular as estruturas de dados para a representação do problema.
• Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)(n+m)). Em particular: complexidades O(sqrt(n)) para o número de fases e O(n+m) para a extração de um conjunto maximal de caminhos aumentantes.
• Decidir experimentalmente: a abordagem por redução para um problema de fluxo é mais eficiente?
• Teste de escalonabilidade: encontrar o “bottleneck matching” em grafos grandes selecionados.

• Um gerador de casos de teste e grafos grandes selecionados são disponíveis aqui.

• As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato DIMACS na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).

Entrega: 31/07/2023

• Implementar o algoritmo de Freivalds.
• Conduzir testes para analisar a probabilidade de sucesso em diferentes matrizes.
• Bonus: determinar empiricamente o tamanho da matriz a partir do qual o Freivalds fica mais eficiente que uma multiplicação simples.
• Bonus: encontrar instâncias com alta probabilidade de falhar.

Entrega: 21/08/2024

• Implementar o teste de primalidade de Miller & Rabin.
• Analisar a complexidade do algoritmo em função de log₂(n) experimentalmente.
• Analisar a probabilidade de responder erradamente “sim” experimentalmente.

• Números inteiros positivos aleatórios.

• As implementações do algoritmo devem ler um número decimal com até 1000 dígitos da entrada padrão e imprimir “s” na saída padrão caso o número é considerado primo e “n” caso contrário.

• Um exemplo trabalhar com números grandes usando a biblioteca GNU MP é disponível em aqui.