Lista de Exercicios AED2 - Algoritmos de Ordenacao e Programacao Dinamica

Exercício de Casa 1 Algoritmos e Estruturas de Dados II 20242 Questão 1 Considere o algoritmo a seguir Algoritmo MISTERIO Entrada Array de inteiros A de tamanho n se n1 então retorne A0 senão retorne maxMISTERIOA0n21 MISTERIOAn2n1 fim se A Qual é o problema resolvido pelo algoritmo MISTERIO B Qual é o paradigma utilizado no algoritmo C Desenhe a árvore de recursão que corresponde à chamada de MISTERIO para o array Anote em cada nó da árvore de recursão qual é o valor 𝐴 7 1 22 4 8 6 3 retornado pela chamada de função que corresponde a esse nó Questão 2 Você possui um dispositivo de armazenamento removível pen drive com capacidade de 𝐺 gigabytes onde é um número inteiro Há uma lista de documentos e o 𝐺 𝑛 𝐷1 𝐷2 𝐷𝑛 𝑖 ésimo documento ocupa megabytes Como é menor que a soma de todos os 𝐷𝑖 𝑚𝑖 𝐺 𝑚𝑖 você não pode salvar todos os documentos no pen drive Seu objetivo é maximizar a utilização do pen drive ou seja salvar o maior número possível de documentos sem exceder sua capacidade de gigabytes 𝐺 Escreva um algoritmo em pseudocódigo de programação dinâmica para esse problema que receba como entrada um de inteiros representando os tamanhos dos 𝑚1 𝑛 documentos e um inteiro positivo representando a capacidade do pen drive Seu 𝐺 algoritmo deve fornecer como saída um único valor numérico representando a utilização máxima do pen drive Analise a complexidade do seu algoritmo Dica Para resolver o problema usando programação dinâmica crie uma matriz bidimensional onde convertendo para megabytes 𝑂𝑃𝑇0 𝑛0 𝑀 𝑀 𝐺 1024 𝐺 Note que 𝑂𝑃𝑇𝑖𝑗 representa a utilização máxima do pen drive considerando os primeiros 𝑖 documentos e uma capacidade máxima de megabytes 𝑗 Questão 3 Considere um array 𝐴0 𝑛 construído pelo seguinte processo começamos com 𝑛 elementos distintos ordenamos esses elementos e em seguida rotacionamos o array 𝑘 passos para a direita Por exemplo podemos começar com o array ordenado 1 4 5 9 10 e rotacionálo passos para a direita obtendo 5 9 10 1 4 𝑘 3 Escreva um algoritmo em pseudocódigo que funcione em tempo Olog n para encontrar e retornar a posição de um elemento no array ou retorne None caso não esteja 𝑥 𝐴 𝑥 presente em Note que seu algoritmo recebe o array mas não conhece o valor de 𝐴 𝐴0 𝑛 𝑘 Questão 4 Alice suspeita que sua rede doméstica está sob ataque cibernético e quer investigar os arquivos de log gerados pelos dispositivos e aplicações da rede Contudo devido à capacidade limitada de armazenamento ela não pode processar todos os arquivos disponíveis Para isso ela classifica os arquivos em três níveis de criticidade 1 crítico 2 alto e 3 moderado tal que 1 crit 2 crit 3 onde crit significa mais crítico que Cada arquivo possui também um tamanho representando o número de eventos Alice deseja processar o maior número possível de eventos respeitando o limite máximo de armazenamento e priorizando os arquivos mais críticos Escreva um algoritmo em 𝑘 pseudocódigo que resolva o problema e receba como entrada um inteiro correspondente 𝑘 a capacidade máxima de armazenamento um inteiro 𝑚 que é o número de arquivos e 𝑚 linhas cada uma contendo dois inteiros criticidade 1 2 ou 3 e tamanho do arquivo 1 A saída do seu algoritmo deve ser o número máximo de eventos que podem 𝑛 10 5 ser processados respeitando o limite e priorizando os arquivos mais críticos Calcule a 𝑘 complexidade de tempo e espaço do seu algoritmo e apresente uma prova de corretude justificando que o algoritmo encontra a solução ótima Questão 5 Qual é a solução da relação de recorrência 𝑇𝑛 3𝑇 𝑛 4 𝑛 2