Existirão dois projectos durante o semestre (ver Métodos de Avaliação).

Os projectos têm sempre duas componentes de avaliação:
Em ambos os projectos, os testes têm dificuldade crescente de forma a que apenas soluções eficientes consigam ter a pontuação máxima.
Os grupos para os projectos:
  • podem ser compostos por 1 ou 2 alunos
  • após abertura do Mooshak, depois de se inscreverem no Fénix avisem-me por email para eu adicionar o grupo ao Mooshak!
  • grupos definidos para o projecto 1, são obrigatoriamente mantidos para o projecto 2
Em ambos os projectos irá ser corrido software de detecção de cópias.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

1º Projecto

Datas:
  • Publicação do enunciado: 03 de Dezembro de 2021
  • Entrega: 04 11 de Janeiro de 2022
Enunciado: p1.pdf
  • Versão 2021-12-10: p1.20211210.pdf onde deixamos cair a contagem do # de sub-sequências no Problema 2, dado que o tempo estimado de resolução claramente excedia as 15h previstas.
Gerador de instâncias: random_k.cpp
  • Compilação: g++ -O3 -Wall -o random_k random_k.cpp -lm
  • Execução: ./random_k 2 10 0.999 200 300 > testfile (podem variar os parâmetros e gerar vários ficheiros de teste)
Vosso projecto:
  • Compilação: g++ -std=c++11 -O3 -Wall file.cpp -lm
  • Execução: ./a.out < testfile (para testar cada um dos ficheiros de teste)
Relatório:
  • Template (2 páginas max) já contém as secções necessárias: link
Esclarecimento adicional sobre a complexidade dos algoritmos a desenvolver para obtenção da cotação máxima no projecto:
  • Problema 1: quadrática
  • Problema 2: cúbica
Observação 1: Recomendamos a aplicação de um pré-processamento de custo linear sobre os inputs que conduza a uma melhoria de performance do algoritmo.
Observação 2: O teste P1_16 está incorrectamente etiquetado como sendo Problema 1 (Prefixo P1) quando se trata efectivamente de um teste do Problema 2. As limitações do sistema Mooshak impedem-nos de re-nomear o teste sem re-iniciar as submissões, pelo que o nome se vai manter.

Solução:

---------------------------------------------------------------------------------------------------------------------------------------------------------

2º Projecto

Datas:
  • Publicação do enunciado: 14 de Janeiro de 2022
  • Entrega: 28 de Janeiro de 2022 (17h00)
Enunciado: p2.pdf

Gerador de instâncias: randGeneoTree.cpp
  • Compilação: g++ -std=c++11 -O3 -Wall randGeneoTree.cpp -lm -o randGeneoTree
  • Execução: ./randGeneoTree 1000 0.9 > testfile (podem variar os parâmetros e gerar vários ficheiros de teste)
Vosso projecto:
  • Compilação: g++ -std=c++11 -O3 -Wall file.cpp -lm
  • Execução: ./a.out < testfile (para testar cada um dos ficheiros de teste)
Relatório:
  • Template (2 páginas max) já contém as secções necessárias: link
Solução:
  • Duas possíveis soluções em C++ (existiam outras abordagens utilizando 3 DFSs, etc...)