Lista de Exercicios - Analise de Algoritmos e Estruturas de Dados

Questão 3 Considere o algoritmo a seguir Algoritmo ALG Entrada Array de inteiros A de tamanho n se n1 então retorne A0 senão retorne maxALGA0 ln21 ALGAln2 n1 fim se A Qual é o problema resolvido pelo algoritmo ALG B Qual é o paradigma utilizado no algoritmo C Desenhe a árvore de recursão que corresponde à chamada de ALG para o array A 7 1 22 4 8 6 3 Anote em cada nó da árvore de recursão qual é o valor retornado pela chamada de função que corresponde a esse nó Questão 4 Suponha que você tenha que escolher entre três algoritmos para resolver um problema O algoritmo A resolve uma instância de tamanho n resolvendo recursivamente oito instâncias de tamanho n2 e combinando suas soluções em tempo On³ O algoritmo B resolve uma instância de tamanho n resolvendo recursivamente vinte instâncias de tamanho n3 e combinando suas soluções em tempo On² O algoritmo C resolve uma instância de tamanho n resolvendo recursivamente duas instâncias de tamanho 2n e combinando suas soluções em tempo On Qual é preferível e por quê Questão 5 Seja dado um conjunto de inteiros positivos e negativos A a1 a2 an Seu objetiva encontrar a subsequência contígua de A com soma máxima ou seja dois índices 1 i j n que maximizam a soma ai ai1 aj1 aj a Descreva um algoritmo On³ para resolver este problema b Descreva um algoritmo On² para resolver este problema c Descreva um algoritmo On para resolver o problema Dica use programação dinâmica de forma similar ao problema da maior subsequência crescente Questão 6 Marque V ou F para cada uma das seguintes afirmações e explique brevemente o porquê Quanto melhor o seu argumento maior a sua nota Sua justificativa vale mais pontos do que sua designação de verdadeiro ou falso 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