✅: recebido. 📝 : avaliado. 🧠 : intenção.

• 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 dos resultados
• O código fonte da implementação
• Arquivos CSV com todos dados experimentais

Entrega: 26 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

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

Entrega: 23 de abril de 2025.

• Implementar a família de algoritmos do tipo Ford-Fulkerson para encontrar o fluxo máximo s-t.
  1. Estratégias de encontrar caminhos: maior gargalo (fattest path), caminho mais curto (BFS), DFS randomizado
• Verificar a complexidade do algoritmo experimentalmente em termos
  1. Número de iterações.
  2. Número de operações (i.e.~número de vértices e arcos “tocados”).
  3. Tempo.
• Analisar a deficiência das iterações e do custo por iteração com a complexidade pessimista.

• 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.
• Repositório com alguns códigos de suporte.

Entrega: 7 de maio de 2025.

• Resolver o problema de vencer um torneio via redução para um problema de fluxo (ver Notas de Aula).
• Conduzir experimentos que determinam
  1. O tempo em função do número de equipes
  2. a probabilidade de vencer o torneio em função do viés da 1a equipe ganhar e o fração de jogos que já aconteceram.

• Um gerador de casos de teste C é disponível aqui.

• As implementações do algoritmo devem aceitar uma instância no formato do gerador na entrada padrão (stdin) e imprimir “sim” caso é possível vencer, ou “não” caso contrário na saída padrão (stdout).

Entrega: 21 de maio de 2025.

• Implementar o algoritmo Húngaro que resolve o problema do emparelhamento de maior peso em grafos bi-partidos ponderados.
• 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(n(m+n log n)), usando o algoritmo de Johnson para busca de caminhos aumentantes.

• Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente no intervalo [0,n^2].
• Para comparar com emparelhamento perfeito máximo: multiplicar os valores por -1.
• Um plano de teste razoável pode conter, por exemplo: i) uma avaliação nível do laço principal, ii) uma avaliação do defeito no nível da busca do caminha M-aumentante, iii) uma avalição da escalonabilidade do algoritmo.

• As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado completo na entrada padrão (stdin) e imprimir (somente!) o valor de um emparelhamento perfeito de peso mínimo na saída padrão (stdout).

• 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 dos resultados.
• O código fonte da implementação.
• Arquivos csv com todos dados experimentais.

• Gerador de instâncias, casos de teste, e documentação adicional.

Entrega: 11/06/2025

• Implementar o Algoritmo 1 de He e Xu.
• Conduzir testes para analisar o desempenho empirico em comparação com a programação dinâmica tradicional do problema da mochila.
• Conduzir testes para analisar a probabilidade de sucesso em diferentes instâncias.
• Bonus: comparar a probabilidade empírica com a probabilidade obtida pela desigualdade de Hoeffding.

• As implementações do algoritmo devem aceitar uma instância da problema da mochila na entrada padrão (stdin) e imprimir (somente!) o valor da melhor solução na saída padrão (stdout). Uma instância é descrito por “n W” na primeira linha, valores p1,…,pn na segunda linha, e pesos w1,…,wn na terceira linha.

• 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 dos resultados.
• O código fonte da implementação
• Arquivos csv com todos dados experimentais.