===== Status =====

^ Nome ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^
| Augusto        | ✓✓  |      |     |     |    | 
| Daniel         | ✓✓  | ✓✓   | ✓   | ✓   |    | 
| Gabriel        | ✓✓  | ✓✓   | ✓   | ✓   |    | 
| Ricardo        |     |      |     |     |    | 
| Victor         | ✓✓  | ✓✓   | ✓   | ✓   |    | 

✓: recebido.  ✓✓ : avaliado.

===== Trabalho 1 (Heaps k-ários e algoritmo de Dijkstra) =====

Entrega: 3 de março 2024.

=== Objetivos ===

  * 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.

=== Casos de teste ===

  * 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 [[http://www.dis.uniroma1.it/~challenge9/download.shtml|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 {{:inf05016:testplan20241.pdf|plano de teste}}.

=== Observações ===

  * 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.

=== Convenções ===

    * 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

=== Entregáveis ===

    * 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

=== Materiais ===

  * {{https://github.com/mrpritt/Caminho_Mais_Curto|Repositório com alguns códigos de suporte}}.

===== Trabalho 2 (Fluxo s-t máximo) =====

Entrega: 10 de julho de 2024.

=== Objetivos ===

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

=== Casos de teste ===

  * Um gerador de casos de teste em formato DIMACS em C é disponível {{https://github.com/mrpritt/Fluxo_Maximo|aqui}}.
  * Exemplo de um {{:inf05016:testplan-flows20241.pdf|plano de teste}}.

=== Convenções ===

  * As implementações do algoritmo devem aceitar uma instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).

==== Gerador de casos de teste ====

  * O {{https://github.com/mrpritt/Fluxo_Maximo|código maxflow.cpp}} calcula o fluxo máximo. Para compilar: Usar C++ e {{http://www.boost.org|Boost}}.

===== Trabalho 3 (Emparelhamentos) =====

Entrega: 23/07/2024

=== Objetivos ===

  * 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.

=== Casos de teste ===

  * Um gerador de casos de teste e grafos grandes selecionados são disponíveis {{https://github.com/mrpritt/Emparelhamento_Maximo/|aqui}}.

=== Convenções ===

  * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato [[http://prolland.free.fr/works/research/dsat/dimacs.html|DIMACS]] na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).

===== Trabalho 4 (Verificação de produtos de matrizes) =====

Entrega: 31/07/2023

=== Objetivos ===

  * 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.

===== Trabalho 5 (Teste de primalidade) =====

Entrega: 21/08/2024

=== Objetivos ===

  * 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.

=== Casos de teste ===

  * Números inteiros positivos aleatórios.

=== Convenções ===

  * 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.

=== Dicas ===

  * Um exemplo trabalhar com números grandes usando a biblioteca [[http://gmplib.org|GNU MP]] é disponível em {{https://github.com/mrpritt/Teste_de_Primalidade|aqui}}.