MC558 - Lab L3

Diretrizes

• Objetivo: Dado um grafo, descobrir se é ou não planar.
• Submissão: Devem ser enviados os seguintes arquivos:
  • Arquivo JSP: a ser desenvolvido durante a aula de laboratório do dia 26/09. Deve ser enviado para o e-mail divulgado na sala, com a tag "[MC558] Lab03", 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 (03/10 [posteriormente adiado para 10/10]), 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 a ser divulgada; o login é o mesmo usado nos labs anteriores). A submissão deve ser feita até quarta que vem (03/10 [posteriormente adiado para 10/10]) à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.
• Entrada: o único parâmetro do programa é o nome do arquivo que especifica um grafo 2-conexo no formato do Lemon.
• Saída: a resposta é dada pela saída padrão (std::cout). Deve ser impresso somente se o grafo é ou não planar. A resposta é dada como "sim\n", no caso do grafo ser planar, e "nao\n" caso contrário. No arquivo em anexo há um exemplo de como deve ser impressa a resposta.
• 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, algumas medidas foram tomadas para que o usuário não fique esperando muito tempo por uma resposta: (1) somente um subconjunto dos casos de teste oficiais é executado e (2) estipulamos um timeout de 10 segundos por caso de teste. Em breve será incluído o teste automático com todas as instâncias oficiais (40 ao total), onde ajustaremos o timeout se necessário.