Estrutura de Dados II - 2021-1
UnB-\(\gamma\)

1.1.1. Tópicos

1.1.2. Material de apoio

1.1.3. Exercícios básicos para relembrar

1.2.1. Entenda os Algoritmos passo a passo

1.2.2. Tempo de execução dos Algoritmos Elementares de Ordenação

1.2.3. Sumarização dos algoritmos

1.2.4. Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na lista pública do CD-MOJ.

   • As credenciais de acesso à lista são as mesmas da primeira. Caso não tenha criado uma conta, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-ordena-elementar
     

2. Implemente
   
   • cada um dos algoritmos discutidos em aula (evite consultar o material e deduza os passos);
3. Compare o tempo de execução dos algoritmos
   
   • Gere entradas aleatórias com 100000 elementos (experimente outras variações de tamanho também)
   • Para gerar uma entrada aleatória em bash

          for((i=0;i<100000;i++)); do echo $RANDOM; done > aleatorio.in
   

   • Caso prefira implementar em C

         srand(time(NULL));
         for(int i=0;i<100000;i++) printf("%d\n",rand());
   

   • compile o código e execute da seguinte forma:

            ./meuprograma > aleatorio.in
     

     • O seu programa deve ler o conjunto de números da entrada padrão, e você poderá verificar o tempo executado através dos comandos:

            time ./bubblesort < aleatorio.in > bubblesort.out
     

     • assim o seu programa irá ler o conteúdo do arquivo aleatorio.in como se fosse digitado pelo teclado e toda a saída será gravada no arquivo bubblesort.out (você pode trocar o nome do arquivo se assim desejar [recomendo um arquivo diferente para cada algoritmo implementado].
     • Crie variações dos arquivos, gere arquivos maiores, menores, ordenados, ordenados reversamente… E compare o tempo entre esses arquivos, há diferença?
4. Verifique a quantidade de operações executadas
   
   • Modifique a sua implementação de forma a mostrar a quantidade de operações de troca e quantas comparações foram feitas.
   • Compare o resultado com todos os algoritmos implementados para diversas entradas
5. Escreva uma função que coloque em ordem lexicográfica um vetor de strings
   
6. Resolva a Terceira questão desta prova
   
7. Resolva a Segunda questão desta prova
   
8. Defina o conceito de estabilidade de um algoritmo de ordenação.
   
   • Liste quais algoritmos trabalhados nesta aula são estáveis e quais não são
9. Ordenando um registro
   

   Suponha que cada elemento de um vetor é um registro com dois campos: um inteiro e outro uma string:

     struct registro { int aa; char *bb;};
   

   Escreva uma função que rearranje o vetor de modo que os campos aa fiquem em ordem crescente. Escreva outra função que rearranje o vetor de modo que os campos bb fiquem em ordem lexicográfica.

10. Execute o benchmark disponibilizado no Github
    

    Faça o git clone do repositório https://github.com/bcribas/benchmark-ordenacao e siga as instruções do README para executar o experimento com algumas implementações.

11. Você pode me ajudar com alguma das issues abaixo?
    
    • https://github.com/bcribas/benchmark-ordenacao/issues/4
    • https://github.com/bcribas/benchmark-ordenacao/issues/6
    • https://github.com/bcribas/benchmark-ordenacao/issues/7
    • https://github.com/bcribas/benchmark-ordenacao/issues/3

1.4.1. MergeSort explicado de outra maneira

1.4.2. Tópicos e materiais

 1:   Item *intercala(Item *a, int la, int ra, Item *b, int lb, int rb)
 2:   {
 3:       //Tamanhos dos vetores a e b
 4:       int ta=(ra-la+1);
 5:       int tb=(rb-lb+1);
 6: 
 7:       Item *c=malloc(sizeof(Item)*(ta+tb));
 8: 
 9:       //intervalos do vetor c
10:       int lc=0;
11:       int rc=(ta+tb-1);
12: 
13:       int ia=la, ib=lb,ic=lc;
14: 
15:       while(ia<=ra && ib<=rb)
16:       {
17:           if(lesseq(a[ia],b[ib]))
18:               c[ic++]=a[ia++];
19:           else
20:               c[ic++]=b[ib++];
21:       }
22:       while(ia<=ra)
23:           c[ic++]=a[ia++];
24:       while(ib<=rb)
25:           c[ic++]=b[ib++];
26:       return c;
27:   }

28:   void mergesort(Item *v,int l,int r)
29:   {
30:       if(l>=r) return;
31:       int meio=(l+r)/2;
32:       mergesort(v,l,meio);
33:       mergesort(v,meio+1,r);
34:       //principal diferença do intercala não ser in-place
35:       Item *c=intercala(v,l,meio,v,meio+1,r);
36:       for(int i=0;i<r-l+1;i++)
37:           v[l++]=c[i];
38:       free(c);
39:   }

1:   Item *c=intercala(&v[l],0,meio-l,&v[meio+1],0,r-(meio+1));

1. Material de apoio
   
   • O aluno também pode acompanhar o material de MergeSort do prof. Paulo Feofiloff
   • Veja a página de comparação dos algoritmos de ordenação
     • https://www.codeproject.com/Articles/5308420/Comparison-of-Sorting-Algorithms

1.4.3. Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na lista Mergesort pública do CD-MOJ.

   • Para ganhar credenciais de acesso à lista, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-mergesort
     

     • Se você já conta para a outra lista (disponibilizada na Aula 1), pode utilizar as mesmas credenciais.
2. Implemente o algoritmo da Intercalação (merge)
   
3. Implemente o algoritmo de ordenaçao por intercalação (mergesort)
   
4. 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.
5. Exercícios baseados do Professor Paulo Feofiloff
   
6. A respeito do problema da Intercalação (merge)
   

   O problema da intercalação (merge) é clássico na computação e consiste em resolver o seguinte problema: dados vetores crescentes v[p .. q-1] e v[q .. r-1], rearranjar v[p .. r-1] em ordem crescente.

   Uma leO é uma lista encadeada que contém uma sequência crescente de números inteiros. Escreva uma função que intercale duas leO dadas, produzindo assim uma terceira leO. Sua função não deve alocar novas células na memória, mas reaproveitar as células das duas listas dadas.

7. Execute o benchmark disponibilizado no Github
   

   Faça o git clone do repositório https://github.com/bcribas/benchmark-ordenacao e siga as instruções do README para executar o experimento com algumas implementações.

   Recomendo que neste momento você execute da seguinte maneira

   TIMEOUT=3 BINARY="dummy bubblesort selectionsort insertionsortslow insertionsort mergesort" make time.reverso time.ordenado
   

   • Após a execução compare a diferença de execução entre os algoritmos e pondere suas implicações
8. Modifique a sua implementação do MergeSort para que ela mostre a quantidade de comparações feitas e compare com execuções feitas com os algoritmos elementares
   
9. O algoritmo MergeSort é estável?
   
10. Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala é estável? E se a comparação lesseq(a[ia],b[ib]), for trocada por less(a[ia],b[ib])?
    
11. Implemente uma versão modificada do MergeSort com que ele considere os números ímpares sempre maiores que os números pares   HOT
    

    • Dessa maneira o vetor, sem ordenação, abaixo:

      30 44 1 93 44 77
      

    • Ficaria ordenado da seguinte maneira:

      30 44 44 1 77 93
      

1.5.1. Corte

1.5.2. Vídeo com TIMESTAMPS

1.5.3. Explicação Número Proibido

1:   int proibidos[140000];
2:   int proibidos_ct;
3:   scanf("%d",&proibidos_ct);
4:   for(int i=0;i<proibidos_ct;i++)
5:     scanf("%d",&proibidos[i]);

 1:   #include <stdio.h>
 2:   #include <stdlib.h>
 3:   int achou(int num,int *v,int l,int r)
 4:   {
 5:     for(int i=l;i<=r;i++)
 6:       if(v[i]==num)
 7:         return 1;
 8:     return 0;
 9:   }
10:   int main(void)
11:   {
12:     int vetor[140000];
13:     //preparando para gerar números aleatórios
14:     srand(140000);
15:     //preenchendo o vetor com números aleatórios inferiores a 1milhão
16:     for(int i=0;i<140000;i++)
17:       vetor[i]=rand()%1000000;
18: 
19:     //fazendo 140000 buscas pelo número 1milhão
20:     for(int i=0;i<140000;i++)
21:       if(!achou(1000000,vetor,0,140000-1))
22:         printf("nao\n");
23:       else
24:         printf("sim\n");
25:   }
26: 

  ribas@jaguapitanga:/tmp$ make busca_bobinha CFLAGS='-O2 -static'
  cc -O2 -static    busca_bobinha.c   -o busca_bobinha
  ribas@jaguapitanga:/tmp$ time ./busca_bobinha > /dev/null

  real  0m15.616s
  user  0m15.607s
  sys   0m0.008s

      TIMEOUT=20 BINARY="bubblesort selectionsort insertionsort mergesort" make time.aleatorio

 1:       #include <stdio.h>
 2:       #include <stdlib.h>
 3:       //Mergesort e Intercala OMITIDOS! Use a versão disponibilizada na Aula 3, seção 3.1
 4: 
 5:       int buscabinaria(int num,int *v,int l,int r)
 6:       {
 7:         if(l>r) return -1;
 8:         int meio=(l+r)/2;
 9:         if(less(v[meio],num))
10:           return achou(num,v,meio+1,r);
11:         else if(lesseq(v[meio],num))
12:           return meio;
13:         else
14:           return achou(num,v,l,meio-1);
15:       }
16:       int main(void)
17:       {
18:         int vetor[140000];
19:         //preparando para gerar números aleatórios
20:         srand(140000);
21:         //preenchendo o vetor com números aleatórios inferiores a 1milhão
22:         for(int i=0;i<140000;i++)
23:           vetor[i]=rand()%1000000;
24: 
25:         //Tenha cuidado com a chamada do MergeSort, o intervalo é FECHADO [l,r]
26:         //por isso é subtraído 1 do tamanho do vetor, para ficar [0,139999]
27:         //que representa os 140000 elementos.
28:         mergesort(vetor,0,140000-1);
29: 
30:         //fazendo 140000 buscas pelo número 1milhão
31:         for(int i=0;i<140000;i++)
32:           if(!buscabinaria(1000000,vetor,0,140000-1))
33:             printf("nao\n");
34:           else
35:             printf("sim\n");
36:       }
37: 

ribas@jaguapitanga:/tmp$ make busca2 CFLAGS='-O2 -static'
cc -O2 -static    busca2.c   -o busca2
ribas@jaguapitanga:/tmp$ time ./busca2 >/dev/null

  real  0m0.032s
  user  0m0.028s
  sys   0m0.005s

1.5.4. LIVE síncrona

1.6.1. Lista pública no CD-MOJ

1.7.1. Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na lista QuickSort

   • Para ganhar credenciais de acesso à lista, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-quicksort
     

     • Se você já conta para a outra lista (disponibilizada na Aula 1), pode utilizar as mesmas credenciais.
2. Escreva o algoritmo da separação
   
3. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j-1] <=0 e v[j..r] > 0 para algum j em p..r+1.
   
   • Faz sentido exigir que j esteja em p..r?
   • Procure fazer uma função rápida que não use vetor auxiliar.
   • Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] >=0.
   • Faz sentido exigir que v[j] seja 0?
4. Um vetor v[p..r] está arrumado se existe j em p..r tal que v[p..j-1] <=v[j] < v[j+1..r] . Escreva um algoritmo que decida se v[p..r] está arrumado. Em caso afirmativo, o seu algoritmo deve devolver o valor de j.
   
5. Um programador inexperiente afirma que a seguinte implementação da função de separação rearranja o vetor v[p..r], com p < r, e devolve um índice j em p..r-1 tal que v[p..j] <= v[j+1..r].
   

   int sep( int v[], int p, int r) {
      int q, i, j, t;
      i = p; q = (p + r) / 2; j = r;
      do {
         while (v[i] < v[q]) ++i;
         while (v[j] > v[q]) --j;
         if (i <= j) {
            t = v[i], v[i] = v[j], v[j] = t;
            ++i, --j;
         }
      } while (i <= j);
      return i;
   }
   

   Mostre um exemplo onde essa função não dá o resultado esperado. E se trocarmos return i por return i-1? É possível fazer algumas poucas correções de modo que a função dê o resultado esperado?

6. Qual o resultado da função separa quando os elementos de v[p..r] são todos iguais? E quando v[p..r] é crescente? E quando v[p..r] é decrescente? E quando cada elemento de v[p..r] tem um de dois valores possíveis?
   
7. A função separa produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?   HOT
   
8. Escreva uma versão recursiva da função separa.
   
9. Implemente o QuickSort
   
10. Submeta o vetor 77 55 33 99 indexado por 1..4 à função quicksort. Teremos a seguinte sequência de invocações da função (observe a indentação):
    

       quicksort( v,1,4)
           quicksort( v,1,2)
               quicksort( v,1,0)
               quicksort( v,2,2)
           quicksort( v,4,4)
    

    Repita o exercício com o vetor 55 44 22 11 66 33 indexado por 1..6.

11. A função quicksort produz uma ordenação estável do vetor?
    
12. Escreva uma versão não recursiva do algoritmo Quicksort. sol
    
13. Execute todas as variações do QuickSort distribuídas no Benchmark de Ordenação e reflita sobre os resultados
    

1.8.1. Material Adicional

1. Conversa sobre o exercício NMUR
   
2. Visão geral do algoritmo QuickSort e QuickSelect
   

1.9.1. Cortes com problemas resolvidos

1.10.1. Exercícios

1. Veja o material sobre hash do Prof. Paulo Feofiloff
   
2. Você consegue aplicar as ideias de HASH nos exercícios Remoção e Sanidade?
   
3. Você consegue aplicar as ideias de HASH no exercício Eleição U.R.S.A.L?
   
4. Considere as técnicas de busca sequencial, busca binária e busca baseada em hashing:
   
   • Descreva as vantagens e desvantagens de cada uma dessas técnicas, indicando em que situações você usaria cada uma delas.
   • Qual é a eficiência de utilização da memória (relação entre o espaço necessário para dados e o espeço total necessário) para cada método?
5. Sobre Tabelas HASH:
   
   • É possível criar uma função HASH em que é garantido que nunca haverá colisão? Porquê?
   • Quando existe colisão, quais estratégias podem ser utilizadas para contornad esse problema? Quando cada estratégia é melhor utilizada?
6. Resolva os exerícios DESTA PROVA   hot
   

1.11.1. Vídeos adicionais sobre HASH

1.11.2. Exercícios

1. Você consegue aplicar os conhecimentos, adquiridos pelos vídeos acima, no problema Desfile dos Patos (em nossa segunda lista de presença).
   
2. Lista pública no CD-MOJ
   

   • Para ganhar credenciais de acesso à lista, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-hash
     

     • Se você já conta para a outra lista (disponibilizada na Aula 1), pode utilizar as mesmas credenciais.
3. Imagine que você tenha um bug em sua implementação de tabela hash utilizando hash-dupla (double-hashing) de tal forma que a primeira ou a segunda função de hash retornam sempre o mesmo valor (porém diferente de \(0\)). Descreva o que ocorre (exemplo: os custos de inserção e busca permanecem o esperado?) quando:
   
   1. a primeira hash está errada;
   2. a segunda hash está errada;
   3. ambas funções hash estão erradas.
4. Resolva o exerício HASHIT da lista de HASH no CD-MOJ
   

   Veja a discussão deste exercício com o Monitor Felipe Borges

5. Resolva o exercício Desfile dos Patos com o seguinte algoritmo
   
   • https://www.cs.utexas.edu/~moore/best-ideas/mjrty/

1.14.1. Vídeos de apoio

1.14.2. Exercícios

1. Lista pública no CD-MOJ
   

   • Para ganhar credenciais de acesso à lista, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-arvorebinaria
     

     • Se você já conta para a outra lista (disponibilizada na Aula 2), pode utilizar as mesmas credenciais.
2. Tente resolver o exercício https://br.spoj.com/problems/PREEMPOS/
   
3. Suponha que as chaves 50 30 70 20 40 60 80 15 25 35 45 36 são inseridas, nesta ordem, numa árvore de busca inicialmente vazia. Desenhe a árvore que resulta.   prof_Feofiloff
   
4. Considere árvores binárias de busca cujos nós têm a estrutura indicada abaixo.   prof_Feofiloff
   

   • Escreva uma função que receba a raiz de uma tal árvore e o endereço de um nó x e devolva o endereço do pai de x.

          typedef struct reg {
         int         chave;
         int         conteudo;
         struct reg *esq, *dir;
          } noh;
     

5. [NÚMERO DE NÓS.] Escreva uma função que calcule o número de nós de uma árvore binária.   prof_Feofiloff
   
6. [FOLHAS.] Escreva uma função que imprima, em ordem in-order, os conteúdos das folhas de uma árvore binária.   prof_Feofiloff
   
7. Dada uma árvore binária, encontrar um nó da árvore cujo conteúdo tenha um dado valor val.   prof_Feofiloff
   
8. [VARREDURA r-e-d.] Escreva uma função que faça a varredura r-e-d (varredura prefixa) de uma árvore binária.   prof_Feofiloff
   
9. [VARREDURA e-d-r.] Escreva uma função que faça varredura e-d-r (varredura posfixa) de uma árvore binária.   prof_Feofiloff
   
10. Escreva uma função para calcular a altura de uma árvore binária
    
11. Escreva uma função que determine a profundidade de um nó dado.   prof_Feofiloff
    
12. Escreva uma função que decida se uma dada árvore binária é quase completa.   prof_Feofiloff
    

1.17.1. Material de apoio

1.17.2. Exercícios

1. Resolva os exercícios de PQ   prof_Feofiloff
   
   • https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/priority.html
2. (SW 9.1) Suponha que a sequência P R I O * R * * I * T * Y * * * Q U E * * * U * E é aplicada a uma PQ de máximo inicialmente vazia. Uma letra significa inserção e um asterisco significa remoção do máximo. Dê a sequência de letras produzida pelas remoções.   Sedgewick
   
3. (SW 9.17) Um vetor em ordem decrescente é um heap decrescente? Um vetor em ordem crescente é um heap crescente?   Sedgewick
   
4. Insira os itens E A S Y Q U E S T I O N, nessa ordem, em um heap decrescente inicialmente vazio. Mostre o heap que resulta.   Sedgewick
   
5. Escreva um método isMaxHeap() para verificar se o vetor pq[] é um heap decrescente. O seu algoritmo deve consumir tempo linear. Repita para heap crescente.   Sedgewick
   
6. Fila priorizada min/max. Projete um tipo-de-dados que dê suporte às seguinte operações: inserção, remoção do mínimo, remoção do máximo, encontrar o mínimo (sem remover), e encontrar o máximo (sem remover). As três primeiras operações devem consumir tempo logarítmico e as duas últimas devem consumir tempo constante. Dica: Use dois heaps.   Sedgewick
   
7. Escreva a API completa de Filas de Prioridade de maneira que ela suporte mais de um Fila de prioridades no seu programa
   
8. Como você pode implementar um algoritmo de Ordenação utilizando o conceito de filas de prioridade?
   
   • Analise e entenda a implementação simples usando fila de prioridades AQUI
   • Pense em como modificar o algoritmo acima para não utilizar memória auxiliar, uma solução está AQUI
9. Rode o conjunto de benchmark de ordenação e idenfique o comportamento dos algoritmos HeapSort e PQsortsimple quando se comparado com o melhor quicksort e o mergesort
   
10. O HeapSort é estável?
    
11. Você é capaz de ressolver esta ISSUE?
    
12. Qual implementação (em vetor ordenado ou não ordenado, com lista encadeada ordenada ou não ordenada, árvore binária em vetor) para encontrar os \(100\) menores elementos de um conjundo de \(10^6\) números aleatórios?   Sedgewick
    
    • Implemente e faça testes de desempenho
13. Resolva o problema Classificados de Sementes utilizando os conceitos de fila de prioridades
    
    • Você pode ler o Enunciado aqui
    • O exercício pode ser resolvido na lista de exercícios de Quicksort
14. É possível resolver o problema kk-página utilizando os conceitos de fila de prioridades?
    
    • Você pode ler o Enunciado aqui
    • O exercício pode ser resolvido na lista de exercícios de Quicksort
15. Resolva o problema Eu posso advinhar a estrutura de dados!   urionlinejudge
    
16. Implemente a ADT de fila de prioridades para fazer a troca baseada em índice (como vimos no fim da última aula)
    

17. Suponha que um vetor está preenchido com as seguintes chaves E A S Y Q U E S T I O N. Imprima o conteúdo do vetor pq e qp após a inserção dos elementos da fila de prioridades implementada no exercício 1.17.2.16
    
18. Adicione a operação remover na sua implementação do problema 1.17.2.16
    
    • esta função serve para quando se remover um elemento qualquer do vetor original
19. Resolva o exercício Churrascarias da Avenida utilizando a implementação feita no exercício 1.17.2.16   spoj br
    

1.20.1. Exercícios

1. Lista pública no CD-MOJ
   

   • Para ganhar credenciais de acesso à lista, envie uma mensagem para @mojinho_bot, no telegram AQUI, com o conteúdo:

     participar bcr-EDA2-2021_1-pq
     

     • Se você já conta para a outra lista (disponibilizada na Aula 2), pode utilizar as mesmas credenciais.

1.23.1. Material de Apoio

1.23.2. TRABALHO 2 - EDAzinho da Dominação

1.26.1. Material de Apoio

1.28.1. Lista pública no CD-MOJ

2.1.1. Revisão de Ponteiros

2.1.2. Strings em C

2.1.3. SCANF

3.4.1. Presença

3.4.2. Menção Final

3.4.3. Critérios de aprovação