Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:
Prazo de submissão: 1 de Junho (submeter no Mooshak de DAA)
Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Nesta aula iremos abordar conceitos de Fluxos Máximos em grafos. Será por isso conveniente ver o que foi falado nas teóricas:
Comece por fazer download do código exemplo do algoritmo de Edmonds-Karp (que funciona em tempo \(\mathcal{O}(|V| \times |E|^2)\)
:Se costuma usar C, a sugestão é que use a última versão, que é essencialmente C com excepção do vector e queue, que já estão implementadas em C++ usando STL. A ideia é que progressivamente possa ir começando a usar as estruturas de dados úteis que o C++ tem e o C não, continuando no essencial a programar em C "normal" e usando C++ apenas para essas estruturas de dados.
Usando como base o código dado no exercício anterior, implemente e submeta uma solução para o problema [DAA 041] Corridas no parque.
Dicas:
Implemente e submeta uma solução para o problema [DAA 042] Clube de livros.
Dicas:
Vamos ficar pelos 42 problemas para submissão no Mooshak :) [e por isso nesta aula não existem problemas complementares]
Se quiser complementar o seu conhecimento sobre fluxos máximos com material que não foi falado na teórica (nem será alvo de avaliação no teste) pode espreitar por exemplo:
Isto serve também para relembrar que apesar de termos coberto muito material nesta unidade curricular, ainda há muitas coisas para aprenderem!
O exercício de desafio desta semana é um pouco diferente e com um espírito mais natalício (originalmente esta UC era dada no 1º semestre). O objectivo é imprimir uma árvore de natal usando o menor programa possível!. A sua pontuação é igual ao tamanho do seu programa (quantidade de bytes): quanto menor melhor!
O prémio para as 3 melhores soluções no final do dia 31 de Julho é um lanche no Alicantina pago por mim, Pedro Ribeiro (mais companhia para pequena conversa sobre algoritmos), a fazer no 1º semestre de 23/24.
Como prémio (e desafio) adicional, o primeiro aluno a conseguir melhorar a minha solução lá submetida (212 bytes) recebe um almoço pago por mim (uma francesinha no Capa Negra II).
Este desafio está disponível para submissão no Mooshak (têm de usar C, C++ ou Java):
Boa época de exames para todos! (e boas férias no final disso)