Lista-de-Exercicios-Analise-de-Algoritmos-Divisao-e-Conquista-e-Programacao-Dinamica

a Verdadeiro Falso Dado um conjunto de inteiros o número de comparações necessárias para encontrar o elemento máximo é n 1 e o número de comparações necessárias para encontrar o elemento mínimo é n 1 Portanto o número de comparações necessárias para encontrar simultaneamente o menor e o maior elemento é 2n 2 b Verdadeiro Falso Em uma solução de programação dinâmica a complexidade de tempo assintótica é sempre pelo menos tão grande quanto o número de subproblemas únicos c Verdadeiro Falso Uma implementação de um problema de programação dinâmica usando a abordagem topdown não produz nenhuma melhoria assintótica para qualquer instância do problema em tempo de execução em relação a uma solução iterativa Questão 7 Seja dado um array de inteiros A a1 a2 an Suponha que exista um índice desconhecido k tal que o subarray a1 ak seja ordenado em ordem estritamente crescente e o subarray ak an seja ordenado em ordem estritamente decrescente ou seja se 1 i j k então ai aj e se k i j n então a aj Seu objetivo é determinar k Descreva um algoritmo em pseudocódigo para resolver este problema e analise seu tempo de execução Dica use Divisão e Conquista Questão 8 Escrever um algoritmo de DIVISÃO E CONQUISTA para o problema da moeda falsa no qual temse n moedas 1 n 10000 uma das quais é falsa sendo seu peso diferente das demais Querse descobrir qual é a moeda falsa usando como auxílio uma balança de pratos Escrever um algoritmo que ilustra o processo de pesagem para descobrir a moeda falsa O número de pesagens feitas deve ser o menor possível Seu algoritmo deve imaginar que as moedas estão numeradas de 1 a n deve receber o número da Moeda falsa f e indicar na saída o processo de pesagem Esse processo tem que fazer sentido não podendo ser simples adivinhação A saída é exemplificada a seguir supondo n 20 e f 17 As explicações entre parêntesis não fazem parte da saída 914 x 1520 conjunto de moedas 15 a 20 mais pesado que 9 a 14 16 x 1520 conjunto de moedas 15 a 20 mais pesado que 1 a 6 1517 x 1820 conjunto de moedas 15 a 17 mais pesado que 18 a 20 15 x 16 moeda 15 de mesmo peso que a 16 Questão 9 Considere a solução buttonup para o Problema da Mochila visto em aula cujo algoritmo encontrase reproduzido a seguir forint i0 in i dpi0 0 forint j0 jw j dp0j 0 forint i1 in i forint j1 jw j ifpesoi1 j dpij dpi1j else dpij maxdpi1j dpi1jpesoi1 valori1