Lista de Exercícios - Análise de Algoritmos e Haskell

Questão 1 Mostre por definição que fn 2n² 3n 4 é On² Questão 2 Mostre por definição que fn n³ não é On² Questão 3 Mostre que 2n1 é O2ⁿ Questão 4 Escreva a equação de recorrência da busca linearsequencial Em seguida resolvaa Questão 5 Escreva a equação de recorrência da busca binária Em seguida resolvaa Questão 6 Escreva a equação de recorrência do melhor caso do Quicksort Em seguida resolvaa Questão 7 Prove que fn gn Omaxfn gn Questão 8 Escreva o algoritmo de ordenação MergeSort em C de forma que ele ordene em ordem decrescente Questão 9 Usando a segunda versão do algoritmo BubbleSort visto em sala que melhoria poderia ser feita para o caso do vetor já estar ordenado Implemente uma terceira versão do algoritmo de forma a levar esse caso em consideração transformando o algoritmo neste caso particular em On Questão 10 Escreva uma função recursiva em Haskell para dada uma lista retornar a soma de todos os elementos dessa lista Questão 11 Escreva uma função recursiva em Haskell para dada uma lista retornar o produto de todos os elementos dessa lista Questão 12 Escreva uma função recursiva em Haskell que recebe dois inteiros base e expoente e retorna o resultado da potenciação Questão 13 Escreva uma função recursiva em Haskell para dada uma lista retornar o tamanho dela