Mooshak #02 - Ordenação e Pesquisa Binária
(semana de 15/11 a 19/11)
Nota Inicial
Os exercício do Mooshak desta aula não contam para nota e são completamente opcionais (a vossa prioridade deve ser primeiro completar os exercícios base das aulas práticas). Os exercícios aqui colocados destinam-se a quem quer ir mais além do que requisitos mínimos e quiser ter uma camada de submissão com avaliação automática, sendo que todas as semanas iremos colocar disponíveis novos problemas.
Para tornar tudo um pouco mais interessante, eu (Pedro Ribeiro) deixo desde já prometido que irei pagar uma refeição na minha companhia (uma francesinha no Capa Negra II) a três estudantes desta UC:
Os 2 estudantes com mais problemas corretamente submetidos no final do semestre (sob um código de conduta de não tentarem simplesmente "copiar código").
Um outro estudante que se tenha destacado nesta componente, segundo a minha avaliação (ex: resolveu os problemas mais difíceis, teve o código mais criativo, etc).
Espero para ver os vosses "dotes" algorítmicos ao longo destas semanas! :)
Problemas para submissão
Nesta unidade curricular vamos usar o sistema Mooshak como uma maneira opcional e adicional para avaliar automaticamente código.
Nesta aula foram disponibilizados os seguintes problemas:
Exercício 1) Usando a biblioteca do C++ 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 biblioteca padrão uma função de ordenação. O C++ não é excepção e o objectivo deste exercício é levá-lo a conhecer como ordenar usando o sort disponível:
Tem ao seu dispor um pequeno programa que mostra como ordenar números inteiros: sort.cpp. 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.cpp. Tem também disponível um ficheiro com um exemplo de input para poder testar o programa: persons.txt. 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 vector 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 vector aumentar a frequência (por exemplo, se a letra for c, basta mexer na posição c-'A' do vector)
Crie uma comparador customizado como no exemplo dado, mas ordenando pelos atributos que o problema pede
Chame o sort e pecorra no final o vector para imprimir o resultado :)
Exercício 3) Um problema com pesquisa binária "clássica"
Comece por ler o enunciado do problema [AED 06] 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 vector v[], queremos todos os pares v[i] + v[j] com 0 ≤ i, j ≤ n-1.
Exactamente quantos pares existem? Qual a sua ordem de grandeza em termos assintóticos?
Implemente dois ciclos para guardar estes pares num novo vector somas[] e confirme que a quantidade de pares é a que calculou.
Para cada uma das Q perguntas vamos querer agora pesquisar no vector 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 vector 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 de C++ 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.
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 - cada pergunta em tempo O(log n2) para resultar em O(Q log n2) no total.
Exercício 4) Um problema com pesquisa binária "indirecta" (binary search the answer)
Use o algoritmo explicado nas aulas teóricas (ver slides da teórica 5 - algoritmos de pesquisa em vetores, The Painter’s Partition Problem, slides 11 a 14; em alternativa pode ver slides equivalentes de uma unidade curricular do DCC/FCUP: ver slides 27 a 36 ou em vídeo.
Conseguir perceber se o custo ≤X pode ser obtido - em tempo O(n)
Fazer pesquisa binária no espaço de respostas possíveis 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 :)
