CANA - Lista de Exercicios 2 ---------------------------- 1) Seja S um vetor nao-ordenado de inteiros (positivos ou negativos). Apresente um algoritmo para encontrar o par x,y de S que "maximize" | x - y |. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2) Seja S um vetor nao-ordenado de inteiros (positivos ou negativos). Apresente um algoritmo para encontrar o par x,y de S que "minimize" | x - y |. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3) Considere um array A de numeros reais. Escreva um algoritmo O(n log n) que encontra um par de elementos (x,y) de A tal que | x + y | e' minimo. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4) Seja um conjunto de n garrafas distintas e n correspondentes rolhas (existe uma correspondencia de 1 para 1 entre garrafas e rolhas). Nao e' permitido comparar duas garrafas ou duas rolhas diretamente, mas e' permitido comparar uma garrafa e uma rolha para saber quem e' a maior das duas. Escreva um algoritmo para encontrar o casamento entre garrafas e rolhas. E' esperado que, no caso medio, a complexidade de seu algoritmo seja O(n log n). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 5) Indique se a seguinte proposicao e' verdadeira ou falsa. Justifique sua resposta. "Existe um algoritmo de ordenacao baseado em comparacoes que ordena uma lista com 6 elementos realizando no maximo 9 comparacoes." - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 6) Dona Ines preparou uma pilha de n tapiocas, p1, ..., pn, e deseja ordenar esta pilha em ordem crescente de tamanho, com a menor tapioca no topo. Uma unica operacao e' possivel: inserir a espatula entre duas tapiocas na pilha e virar. Por exemplo, se ela insere a espatula logo abaixo da tapioca 1, o seguinte cenario e' obtido depois de virar: 2 1 5 3 3 5 1 <________ 2 7 7 6 6 4 4 Desenvolva um algoritmo para resolver o problema de D. Ines que utiliza apenas a operacao de virar para ordenar as tapiocas. E' claro que e' permitido a D. Ines examinar a pilha de tapiocas antes de escolher a posicao de enfiar a espatula. Ela tambem pode reconhecer facilmente qual a menor tapioca entre quaisquer pares de tapioca. Quantas operacoes de virada o seu algoritmo efetua? - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 7) Considere uma sequencia de numeros inteiros com muitos elementos repetidos, contendo apenas O(log n) numeros distintos. a) Apresente um algoritmo para ordenar sequencias deste tipo que execute O(n log log n) comparacoes. b) A existencia deste algoritmo contradiz o teorema que estabele que qualquer algoritmo de ordenacao baseado em comparacoes realiza Omega(n log n) comparacoes? Justifique. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8) Dado um conjunto S com n numeros positivos, dizemos que um par de elementos x, y e' proximo se |x - y| <= {Max S - Min S} / (n-1) a) Prove ou de um contra-exemplo para a seguinte proposicao: "Para todo conjunto S existe um par de elementos proximos." b) Faca um algoritmo para encontrar um par de elementos proximos do conjunto S (se existir algum) em tempo b1) O(n log n) b2) O(n) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 9) Um conjunto de pontos e' dito colinear se existe uma unica linha reta que passa por todos os pontos do conjunto. Desenvolva um algoritmo que, dado um conjunto de pontos P = {p1,...,pn}, onde pi = (xi,yi), encontre um subconjunto colinear de tamanho maximo. Seu algoritmo deve executar em tempo O(n^2 logn). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 10) Suponha que voce possui uma lista de n intervalos I1, ..., In. Cada intervalo Ij e' descrito pelos seus limites esquerdo e direito, Ej e Dj respectivamente. O intervalo Ij esta contido no intervalo Ik se Lk < Lj e Dk > Dj. Desenvolva um algoritmo para verificar se existe algum intervalo contido em outro. Se algoritmo deve executar em tempo O(n log n). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 11) Anagramas sao palavras que correspondem a permutacoes distintas do mesmo conjunto de letras. Por exemplo, as palavras MISSA e ASSIM sao anagramas. Suponha que voce possui uma lista com n palavras, cada uma delas formada por m letras. Desenvolva um algoritmo para verificar se existe algum par de anagramas na lista. Seu algoritmo deve executar em tempo O(n*m). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 12) Descreva um algoritmo que ordene uma lista com n elementos utilizando como estruturas de dados duas pilhas e O(1) variaveis locais. Analise o tempo de execucao do seu algoritmo. Prove que nao existe nenhum algoritmo capaz de ordenar uma lista com n elementos utilizando apenas uma pilha e O(1) variaveis locais. Nota: Suponha que no inicio da execucao a lista de elementos esta armazenada em uma das pilhas. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 13) Dada uma lista nao-ordenada de inteiros distintos A = {a1,...,an}, dizemos que um certo elemento x de A e' uma mediana aproximada de A se as seguintes condicoes sao satisfeitas: i) | {i : ai < x} | > n/4 ii) | {j : aj > x} | > n/4 Descreva um algoritmo para encontrar uma mediana aproximada de A que execute em tempo O(n), no pior caso. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 14) Descreva um algoritmo para ordenar vetores da forma |---|-----|---|-|-|-|-|---|-----| |n-k|n-k+1|...|n|1|2|3|...|n-k-1| |---|-----|---|-|-|-|-|---|-----| Seu algoritmo deve obedecer as seguintes restricoes: a) Deve executar em tempo O(n) b) Deve utilizar apenas O(1) variaveis auxiliares. Isto significa que ele nao pode utilizar um vetor auxiliar com n, k ou n-k, elementos. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 15) Considere o problema de determinar se todos os elementos de uma lista A = {a1, ..., an} sao distintos. a) Obtenha um limite inferior para o tempo de execucao de qualquer algoritmo baseado em comparacoes para este problema. b) Repita o exercicio do item anterior para a situacao em que a comparacao informa apenas se os dois elementos sao iguais ou diferentes.