MC558 - Lab L2

Diretrizes

• Objetivo: Dado um grafo K_m,n ponderado nas arestas, encontrar um emparelhamento de peso máximo. Para provar que o emparelhamento tem peso máximo, também é preciso mostrar uma cobertura por vértices de custo mínimo.
• Submissão: Devem ser enviados os seguintes arquivos:
  • Arquivo JSP: a ser desenvolvido durante a aula de laboratório do dia 12/09. Deve ser enviado para o e-mail divulgado na sala, com a tag "[MC558] Lab02", até o final da aula de laboratório.
  • complexidade.pdf: arquivo que descreve a complexidade do algoritmo implementado. Neste arquivo também devem estar as diferenças entre o JSP e a implementação (se houver). Deve ser enviado até quarta que vem (19/09 [posteriormente adiado para 23/09]), como resposta ao e-mail em que foi enviado o JSP.
  • Implementação: conjunto de arquivos *.cpp e *.h, além de um makefile, que devem ser submetidos via servidor (página ainda serão divulgada; o login é o mesmo usado no lab01). A submissão deve ser feita até quarta que vem (19/09 [posteriormente adiado para 23/09]) às 23:59. Ao submeterem, vocês devem organizar todos os arquivos *.cpp e *.h dentro de um arquivo .zip. O arquivo .zip também deve conter um arquivo makefile para compilar o código. Em anexo está um exemplo de submissão.
  • Testes: Durante a submissão é possível testar se o programa está funcionando corretamente. Para isso, o programa é executado com alguns casos de teste pequenos. Como a resposta é computada no momento da submissão, inicialmente colocamos poucos casos de teste, e estipulamos um timeout de 10 segundos por caso de teste, para que o usuário não fique esperando muito tempo por uma resposta. Depois incluiremos os casos de teste oficiais e ajustaremos o timeout, caso seja necessário.
• Critérios de Avaliação: A nota da atividade será a soma das notas obtidas em cada um dos critérios abaixo:
  • JSP: clareza e corretude. Nota entre 0-5.
  • Corretude da Implementação: número de casos de teste executados corretamente. Nota entre 0-3.
  • Running time: será feita uma lista em ordem decrescente do tempo de execução médio para resolver uma instância (tempo total / núm. acertos). Os trabalhos serão separados em dois grupos: Série A, que competirá pelas notas mais altas, e Série B. Nota entre 0-1.
  • Complexidade do algoritmo: verificar se a análise de complexidade do algoritmo está correta (arquivo complexidade.pdf). Nota entre 0-1.
• Sugestão: É possível modificar o Húngaro para aumentar a eficiência em um K_m,n? Nesta atividade não é preciso implementar exatamente o húngaro, pode ser um húngaro modificado, contanto que estas modificações tragam algum ganho.

Mudança nos critérios de avaliação

A razão da mudança de critérios entre o Lab 01 e o Lab 02 é que observamos algumas coisas no Lab 01 que desejamos evitar no futuro.

Uma das coisas que observamos foi que o critério de avaliação não dava tanto valor ao JSP. Como consequência, a pessoa que implementasse algo totalmente diferente de seu JSP acabava não tendo muita desvantagem, pois o que ela perdia no JSP poderia ser ganho em running time e corretude.

Porém, consideramos o JSP muito importante. Para valorizá-lo, resolvemos não só aumentar seu peso relativo (de 3 para 5), como também fazê-lo ser definidor das Séries A e B de running time. Mais especificamente, Série A agora é ter 5.0 ou mais no JSP e Série B é ter até 4.9 no JSP.

Notas

MC558 Home

© 2012 João Meidanis