Lista de Exercicios - Algoritmos e Estruturas de Dados II - Capítulos 4 e 14

Algoritmos e Estruturas de Dados II 20252 Lista de Exercícios Exercícios dos Capítulos 4 e 14 do livro Introduction to Algorithms 4a edição de Thomas H Cormen Questão 1 Marque a alternativa correta A Suponha que você tenha usado duas sequências A e B como dados de entrada para um algoritmo de programação dinâmica que resolve o problema da maior subsequência comum entre duas sequências Como resultado você obteve a sequência C Neste contexto é correto afirmar que Certamente não há outra subsequência comum a A e B com o mesmo comprimento que C Certamente não há subsequência comum a A e B com comprimento menor que C Pode haver uma subsequência comum a A e B com comprimento maior que C mas somente C é uma subsequência de comprimento ótimo Dependendo de A e B pode haver outras sequências com o mesmo comprimento que C NDA B Um algoritmo no qual dividimos o problema em subproblemas e depois combinamos as subsoluções para formar a solução do problema original é conhecido como Força Bruta Divisão e Conquista Programação Dinâmica NDA C Um algoritmo que usa os resultados anteriores para encontrar os novos resultados adota o paradigma Força Bruta Divisão e Conquista Programação Dinâmica NDA Questão 2 Resolva as recorrências a seguir usando o Teorema Mestre A Tn 8Tn2 1000n B Tn 2Tn2 n2 C Tn 3Tn4 n3 D Tn 81Tn9 n4 log n E Tn 4Tn2 log n 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 ALGA ln2 n1 fim se A Qual é o problema resolvido pelo algoritmo ALG