Skip to content

Latest commit

 

History

History
207 lines (152 loc) · 6.68 KB

Lista1.md

File metadata and controls

207 lines (152 loc) · 6.68 KB
Raw

Universidade Federal de Minas Gerais

Disciplina: DCC002 - Algoritmos e Estrutura de Dados 2

Professor: Flavio Vinicius Diniz de Figueiredo

Lista de Exercícios - Prova 1

TADs

  1. Crie um Tipo Abstrato de Dados para Matrizes. Implemente as funções de inicializar a matriz (toda zerada), computar a soma de duas matrizes, subtração de duas matrizes e o determinante de uma matriz quadrada. Seu programa pode indicar um erro caso a matriz passada para o determinante não seja quadrada.

    • Indique a complexidade de todas as funções
    • Justifique as assinaturas de cada função

  2. Crie um TAD para pontos em um espaço n-dimensional (Euclidean space). Implemente funções para inicializar um ponto, computar a distância entre dois pontos, a norma de dois pontos, o ângulo dos pontos e rotacionar o espaço.

Revisão C + Complexidade

  1. Escreva um algoritmo que determina se um número inteiro é primo. Qual é a complexidade do seu algoritmo?

  2. Escreva um que aproxima o logaritmo de um número inteiro para um número outro inteiro cujo valor é próximo do log real. Isto é, arredonde o valor de log para cima ou para baixo. Por exemplo log310 = 2.09. Você pode retornar 2 ou 3. Qual a complexidade da sua função?

    int myLogTosco(int number, int power)

    Não utilize a math.h ou qualquer biblioteca externa. Código C apenas.

  3. Escreva uma função que retorna os x menores números de um vetor. Quando x=1, retornamos apenas o menor número. Quando x=2 retornamos os dois menores. Qual a complexidade da sua função?

    int nSmallest(int *vec, int n, int x)

    n é número de elementos no vetor.

  4. Escreva um algoritmo que compacta uma string. A compactação de uma string é uma operação que simplesmente conta o número de ocorrências de letras na string retornando uma nova string de tamanho menor. Por exemplo, a string:

    aaaaabcdddeeeffffff abc

    É compactada para:

    a5b1c2d3e3f6 3a1b1c1

    Sua função deve ter uma assinatura como:

    char *compacta(char *string)

    Escreva também a função inversa

    char *descompacta(char *string)

    Indique a complexidade das duas funções em termos do tamanho das strings.

  5. Implemente uma função que recebe como entrada um vetor de números inteiros, vec, o tamanho do mesmo n, junto com um número inteiro target. Sua função deve indicar se no vetor vec existem dois elementos cuja soma é target. Por exemplo:

    vec = [10, 20, 3, 45, 0]
target = 65
return 1 //45 + 20 = 65

    vec = [10, 20, 3, 45, 0]
target = 29
return 0 //não existem tais elementos

    Assinatura:

    int existeSoma(int *vec, int n, int target)

    Qual a complexidade da sua função?

    Para simplificar, assuma que target sempre é maior do que todos os elementos do vetor. Isto é, se target = 65 nenhum elemento do vetor tem tamanho maior do que 65.

  6. Escreva uma função que inverte as palavras de uma string. Por exemplo:

    Alice Likes Bob

    é convertido para

    Bob Likes Alice

    Assinatura:

    char *invertWords(char *string)

    Para auxiliar seu método, pode utilizar strtok da string.h. Sua função funciona quando mais de um espaço entre palavras é inserido? Qual a complexidade da sua função?

  7. Escreva uma função para encontrar o local de início de fim de uma substring dentro de outra string. A assinatura da função é:

    void subPosition(char *text, char *sub, int *start, int *end)

    Para uma entrada:

    char *sub = "muito";
char *texto = "Eu gosto muito de AEDS2";

    Seu método deve retornar:

    *start = 9;
*end = 13;

    Qual a complexidade da sua função? A mesma funciona com a entrada:

    char *sub = "aabb";
char *text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabb";

  8. Escreva uma função que indica se duas strings são palíndromas. Qual a complexidade da sua função?

    int palindroma(char *string1, char *string2)

  9. Escreva uma função que indica se duas strings são anagramas. Pode assumir que as palavras serão sempre de [a-z] minúsculo. Qual a complexidade da sua função?

    int anagrama(char *string1, char *string2)

Complexidade

  1. Para cada uma das afirmativas abaixo, diga se a afirmativa é verdadeira (V) ou falsa (F). Em todas as afirmativas, justifique a sua resposta. Respostas sem justificativa não serão consideradas.

    1. Considere um programa P que faz uma série de operações de custo constante, chama uma função F1 com complexidade dada por f(n) e depois chama uma função F2 com complexidade dada por g(n), onde g(n) = 1000 f(n). Pode-se afirmar que o programa P é O(f(n)).

    2. Considere um programa cuja função de complexidade é f(n) = 3 log(n). É correto afirmar que esse programa é O(log n), mas não é O(n2).

    3. Um programa P executa uma função F1 com complexidade f(n) em 50% de suas n interações, e uma função F2 com complexidade g(n) nas demais interações. Portanto, o programa P tem complexidade O(Max (O(f(n), O(g(n))).

    4. Sejam duas funções de complexidade g(n) = 5(n2) + 3n + 4 e f(n) = 95n2 + n + 15. É correto afirmar que um programa P1 cuja complexidade é g(n) é mais rápido que um programa P2, com complexidade f(n).

  2. Considerando que 0 < ε < 1 < c, indique para cada par de expressões (A, B) na tabela abaixo, se B é Ο, Ω, ou Θ de A. Justifique suas respostas.

    A B Complex
    n 3n Θ
    n2 n Ο
    n n3 Ω
    n4 + n + 100 n3 + 1004 ?
    2n 3n/2 ?
    cε (c+1)ε ?
    log(n) sqrt(log(n)) ?