Prazo de submissão: 10 de Abril (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. Relembre 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%.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de ordenação e pesquisa binária. Será por isso conveniente ver o que foi falado nas teóricas:
Exercício 1) Usando a biblioteca da sua linguagem para ordenar
A ordenação é uma operação "básica" essencial em muitos algoritmos. É por isso comum que uma qualquer linguagem de programação tenha disponível na sua bilbioteca padrão uma função de ordenação, O objectivo deste exercício é levá-lo a conhecer como ordenar usando o sort disponível na sua linguagem preferida.
Iremos usar as seguintes funções (escolha a da linguagem que pretende usar):
Tem ao seu dispor um pequeno programa que mostra como ordenar números inteiros: sort.c, sort.cpp ou Sort.java. Descarregue o código da sua linguagem de eleição e experimente compilar e executar na sua máquina, garantindo que percebe o programa.
A mesma função de ordenação pode ser usada para quaisquer outros tipo primitivos. Experimente mudar o programa para outro tipo primitivo (ex: double ou char) e execute para verificar que a ordenação continua a funcionar.
Exercício 2) Ordenação com um critério personalizado
Por vezes queremos ordenar por um critério diferente do padrão (ex: por ordem decrescente; ordenar primeiro por um campo e depois por outro). Nesses casos queremos poder usar o sort da biblioteca, mas passar-lhe um comparador "customizado" que permita ordenar segundo o critério que desejamos.
Tem ao seu dispor um pequeno programa para ordenar pessoas por ordem crescente da idade e em caso de empate por ordem alfabética do nome: customsort.c, customsort.cpp ou CustomSort.java. Tem também disponível um ficheiro com um exemplo de input para poder testar o programa: persons.txt. Descarregue o código da sua linguagem de eleição e experimente compilar e executar na sua máquina, garantindo que percebe o programa.
O que precisaria de alterar no programa para ordenar por ordem decrescente da idade (ao invés da ordem crescente)? Experimente mudar, compilar e executar para testar o que pensou.
Crie uma classe/estrutura para representar uma letra, contendo como atributos a frequência, a posição da primeira ocorrência e a letra em si
Crie um array de objectos/estruturas do tipo anterior, com espaço para cada uma das 26 letras: na posição 0 o 'A', na posição 1 o 'B', etc; não se esqueça de garantir de inicializar os atributos no início
Depois de ler o fragmento de ADN, basta percorrê-lo e na posição correspondente do array aumentar a frequência (por exemplo, se a letra for c, basta mexer na posição c-'A' do array)
Crie uma comparador customizado como no exemplo dado, mas ordenando pelos atributos que o problema pede
Chame o sort e pecorra no final o array para imprimir o resultado :)
Exercício 3) Um problema com pesquisa binária "clássica"
Comece por ler o enunciado do problema [DAA 010] Somas mais próximas. O objectivo final deste exercício é conseguir submeter com sucesso uma solução. Em vez de considerar que são possíveis spoilers, neste problema queremos mesmo que siga os passos que sugerimos.
Vamos começar por calcular todos as somas possíveis de pares de números. Se temos n números guardados num array v[], queremos todos os pares v[i] + v[j] com 0 ≤ i, j ≤ n-1.
Exactamente quantos pares existem? (use o seu conhecimento sobre somatórios e progressões aritméticas obtido no capítulo anterior de matéria). Qual a sua ordem de grandeza em termos assintóticos?
Implemente dois ciclos para guardar estes pares num novo array somas[] e confirme que a quantidade de pares é a que calculou..
Para cada uma das Q perguntas vamos querer agora pesquisar no array pares[] procurando a(s) soma(s) mais próxima(s).
Uma alternativa seria fazer uma simples pesquisa linear (um ciclo percorrendo todos os elementos de pares). Será que isto passaria no tempo necessário? Porquê?
O array de somas é igual para todas as perguntas pelo que podemos pré-processar para depois melhorar a pesquisa. Sendo assim, podemos precisamente... ordená-lo! Use a biblioteca padrão da sua linguagem para ordenar o array.
Depois de ter ordenado, podemos aplicar... pesquisa binária! É no entanto necessário cuidado porque o número que procuramos pode não estar no array. O que queremos realmente é o número mais próximo do que procuramos. Que versão da pesquisa binária dada nas aulas teóricas será mais útil para esta tarefa? [ver slides 23 a 26]
No final, o esquema geral do algoritmo para este problema é o seguinte:
Calcular a soma de todos os pares - em tempo O(n2).
Ordenar as somas dos pares - em tempo O(n2 log n2).
Para cada uma das Q perguntas, fazer uma pesquisa binária - em tempo O(log n2).
Exercício 4) Um problema com pesquisa binária "indirecta" (binary search the answer)
Conseguir perceber se o custo ≤X pode ser obtido - em tempo O(n)
Fazer pesquisa binária a X (qual o intervalo onde X pode estar?)
Exercício de Desafio
Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.
Para esta semana o desafio é diferente do habitual, sendo um problema de output-only, pelo que pode resolvê-lo usando uma qualquer linguagem de programação (ou até fazendo manualmente). O problema está disponível para submissão no Mooshak:
Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas, sabendo que este problema é substancialmente mais difícil os outros desta aula.
Depois de terem submetido não deixem de falar comigo no Slack para explicarem as vossas ideias, uma vez que não vou ter acesso ao código que usaram para gerar a resposta :)
