Algoritmos e Estrutura de Dados I - AE22CP - 2013/1

Bruno César Ribas

Exercícios

  1. O que é Algoritmo?

Merge

  1. Implemente o algoritmo da Intercalação (merge)

  2. Resolva a questão 3 da Prova Substitutiva da Segunda prova de 2012-1

  3. Escreva uma função que receba vetores disjuntos x[0..m-1] e y[0..n-1], ambos em ordem crescente, e produza um vetor z[0..m+n-1] que contenha o resultado da intercalação dos dois vetores dados. (É claro que z estará em ordem crescente). Escreva duas versões da função: uma iterativa e uma recursiva.

  4. Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala1 discutida acima é estável? E se a comparação "v[i] <= v[j]" for trocada por "v[i] < v[j]"?

  5. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
         i = p; j = q; k = 0;
         while (i < q && j < r) {
            if (v[i] <= v[j])  w[k++] = v[i++];
            if (v[i] > v[j]) w[k++] = v[j++];
         }
         while (i < q)  w[k++] = v[i++];
         while (j < r)  w[k++] = v[j++];
         for (i = p; i < r; ++i)  v[i] = w[i-p]; 
    

  6. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
         i = p; j = q; k = 0;
         while (i < q && j < r) {
            if (v[i] <= v[j])  w[k++] = v[i++];
            else  w[k++] = v[j++];
         }
         while (i < q)  w[k++] = v[i++];
         for (i = p; i < j; ++i)  v[i] = w[i-p]; 
    

  7. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
         i = p; j = q;
         for (k = 0; k < r-p; ++k) {
            if (j >= r || (i < q && v[i] <= v[j])) 
               w[k] = v[i++];
            else 
               w[k] = v[j++]; 
         }
         for (i = p; i < r; ++i)  v[i] = w[i-p]; 
    

  8. Critique a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
         i = p; j = q; k = 0;
         while (k < r-p) {
            while (i < q && v[i] <= v[j]) 
               w[k++] = v[i++];
            while (j < r && v[j] <= v[i]) 
               w[k++] = v[j++];
         }
         for (i = p; i < r; ++i)  v[i] = w[i-p];