Objectivos para o Teste Prático 1 (28 de Abril)
Aqui fica uma lista de objectivos para o 1º teste prático de DAA, que incidirá sobre os capítulos 1 a 4. Poderá implementar as soluções em C, C++ ou Java.
Formato:
- Data: 28 de Abril do 2022 (quinta-feira)
- Horário: 18:15
- Duração: 2h
- Local: Laboratórios do DCC/FCUP
- Valorização: 2.5 valores (como explicado em avaliação)
Informações para o teste:
Podem (pré)submeter um ficheiro com código (e qualquer texto que queiram), ao qual terão acesso durante o teste - ir ao concurso "1º Teste Prático - Pré-Submissão de Código" e submeter um único ficheiro; se submeterem mais do que uma vez, apenas a última submissão estará disponível no dia do teste prático; o ficheiro (.txt) pode conter o que quiserem até um máximo de 500KB (até 23:59 de quarta, dia 27 de Abril).
As pontuações são parciais, significando que cada problema terá vários testes, cada um valendo um determinado número de pontos. Para cada teste pontuável existirá um teste não pontuável de características similares disponível para visualização quando falharem. Os testes pontuáveis são secretos. A sua pontuação é determinada pelos testes em que o seu programa acertar. Para terem 100% num problema será necessário terem uma solução eficiente. Uma solução com "força bruta" poderá portanto dar menos do que a pontuação ótima.
Os enunciados estão "despidos" da uma história mais gira para irem directos ao que é pedido de modo a que possam usar as duas horas de forma adequada. Para alguns dos problemas poderão ser dadas dicas sobre como resolver.
Terão acesso a documentação das vossa linguagens e às classes FastScanner e FastPrint, no Java.
O teste prático terá os seguintes 3+1 problemas para serem resolvidos em 2h (o último problema é para ter nota acima de 100%):
Problema A (34% da nota)
Greedy + Ordenação
- Será pedido que resolva um problema que admite uma solução greedy
- Será dito explicitamente no teste qual a escolha greedy que deve fazer
- A escolha greedy passará por ordenar números e/ou strings segundo um critério customizado
- Os elementos a ordenar poderão ter números e/ou strings
- Para terem 100% dos pontos neste problema é necessária uma ordenação O(n log n)
- Uma ordenação quadrática terá sensivelmente 40% dos pontos
- É aconselhável que use a API de ordenação disponibilizada pela sua linguagem (qsort no C, sort no C++, Arrays.sort no Java)
Problemas exemplo: - [DAA 014] O Problema do sapateiro (se saisse no teste seria explicado qual o critério a usar para ordenar as encomendas de sapatos) - [DAA 009] ADN alienígena (um outro problema onde é preciso usar ordenação customizada) - [DAA 013] Cobertura mínima (um outro problema greedy onde é necessário usar ordenação)
Problema B (33% da nota)
Pesquisa Binária
- Deverá saber aplicar um variante de pesquisa binária directa ou indirecta
- Neste problema os dados já estão ordenados
- Para terem 100% dos pontos neste problema é necessária uma parte de pesquisa O(log n)
- Uma pesquisa linear terá sensivelmente 40% dos pontos
- A pesquisa binária terá de ser feita manualmente (não podem usar funções como o bsearch do C, o lower_bound do C++ ou o Arrays.BinarySearch do Java, ou estruturas de dados avançadas como sets ou maps)
Problemas exemplo: - [DAA 010] Somas mais próximas - [DAA 011] Viagem de mochila às costas (mais complicado do que posso vir a colocar no teste como problema B)
Problema C (33% da nota)
Programação Dinâmica
- Deverá saber aplicar um algoritmo "básico" de programação dinámica
- O problema será semelhante a um ou mais dos sequintes problemas dados nas teóricas:
- Pirâmides
- Maior Subsequência Crescente
- Troco de Moedas
- Obras na Estrada
- Jogo de Pedras
- Para terem 100% dos pontos neste problema é necessário terem uma solução polinomial.
- Uma solução exaustiva exponencial terá sensivelmente 40% dos pontos
Problemas exemplo: - [DAA 017] Pirâmides - [DAA 018] Troco de moedas
Problema D (20% da nota)
Tema Aberto
- Este problema pode dar 20% adicionais (0.5 valores), ou seja, é possível ter nota acima dos 2.5 valores (por exemplo para compensar algo que corra menos bem noutro componente da avaliação)
- É um problema um pouco mais complicado que os anteriores, sem dicas dadas no enunciado, e que só deverá ser tentado depois de resolvidos os outros três
- Pode usar uma combinação de um ou mais elementos entre dividir para conquistar, ordenação, pesquisa binária, algoritmos greedy, programação dinâmica e árvores de pesquisa equilibradas
)