Estrutura de Dados II - 2020-2
UnB-\(\gamma\)

1.1.1 Tópicos

1.1.2 Material de apoio

1.2.1 Tópicos e materiais

1.2.2 Entenda os Algoritmos passo a passo

1.2.3 Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na lista 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-2020_2-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.

1.3.1 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.3.2 Veja também

1.3.3 Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na SEGUNDA lista 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-2020_2-ordena-rapido-e-busca
     

     • Se você já conta para a outra lista (disponibilizada na Aula 2), 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
   

1.4.1 Tópicos e Materiais

1.4.2 Vídeos adicionais

1.4.3 Exercícios

1. 1a lista de exercícios de fixação no MOJ
   
2. 2a lista de exercícios de fixação no MOJ
   
3. Primeira lista de presença
   
   • Credenciais enviadas para o email institucional
   • A lista está disponível em https://moj.naquadah.com.br/cgi-bin/contest.sh/bcr-EDA2-2020_2-presenca-1
   • A lista contempla os dias 01 03 08 10 e 17 de fevereiro
   • Você deverá ACERTAR o exercício garantir 10% de acerto para receber a presença

1.5.1 Exercícios

1. Resolva os exercícios propostos das aulas anteriores
   
2. O algoritmo MergeSort é estável?
   
3. Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala discutida na Aula 3 é estável? E se a comparação lesseq(a[ia],b[ib]), for trocada por less(a[ia],b[ib])?
   
4. 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.7.1 O QuickSort

1.7.2 Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na TERCEIRA lista 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-2020_2-quick
     

     • Se você já conta para a outra lista (disponibilizada na Aula 2), pode utilizar as mesmas credenciais.
2. Assista aos vídeos sobre QuickSort no youtube (elencados na seção anterior)
   

1.8.1 Exercícios

1. Escreca o algoritmo da separação
   
2. 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?
3. 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.
   
4. 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?

5. 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?
   
6. A função separa produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?   HOT
   
7. Escreva uma versão recursiva da função separa.
   
8. Implemente o QuickSort
   
9. 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.

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

1.9.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. Você consegue aplicar os conhecimentos, adquiridos pelos vídeos acima, no problema Desfile dos Patos (em nossa segunda lista de presença).
   

1.10.1 Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na QUARTA lista 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-2020_2-hash
     

     • Se você já conta para a outra lista (disponibilizada na Aula 2), pode utilizar as mesmas credenciais.
2. 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?
3. 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?
4. Resolva os exerícios DESTA PROVA   hot
   

1.11.1 Exercícios

1. 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.
2. Resolva o exerício HASHIT da quarta lista de exerícios de fixação.
   

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

3. Resolva o exercício da Lista de Presença, Desfile dos Patos com o seguinte algoritmo
   
   • https://www.cs.utexas.edu/~moore/best-ideas/mjrty/

1.13.1 Vídeos de apoio

1.13.2 Exercícios

1. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na QUINTA lista 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-2020_2-5alista
     

     • 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/
   

1.14.1 Exercícios

1. Lista de presença para o dia 22 de março está no moj
   
   • https://moj.naquadah.com.br/cgi-bin/contest.sh/bcr-EDA2-2020_2-presenca-4
     • utilize os mesmos logins das listas de presença
2. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na SEXTA lista 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-2020_2-6alista
     

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

1.15.1 Exercícios

1. Lista de presença para o dia 29 de março está no moj
   
   • https://moj.naquadah.com.br/cgi-bin/contest.sh/bcr-EDA2-2020_2-presenca-5
     • utilize os mesmos logins das listas de presença
2. Lista pública no CD-MOJ
   
   • Resolva os exercícios propostos na SEXTA lista 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-2020_2-6alista
     

     • Se você já possui conta para a outra lista (disponibilizada na Aula 2), pode utilizar as mesmas credenciais.
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.16.1 Material de apoio

1.16.2 Exercícios

1. Lista de presença para o dia 29 de março está no moj
   
   • https://moj.naquadah.com.br/cgi-bin/contest.sh/bcr-EDA2-2020_2-presenca-6
     • utilize os mesmos logins das listas de presença
2. Resolva os exercícios de PQ   prof_Feofiloff
   
   • https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/priority.html

1.18.1 Exercícios

1. Resolva a Sétima Lista de presença   MOJ
   
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 3a lista de exercícios de fixação
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 3a lista de exercícios de fixação
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.18.1.16
    
18. Adicione a operação remover na sua implementação do problema 1.18.1.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.18.1.16   spoj br
    

1.21.1 Material de Apoio

1.21.2 Exercícios

1. Resolva a Oitava Lista de presença   MOJ
   

1.25.1 Material de Apoio

1.25.2 Exercícios

1. Resolva os exercícios A,B,C,F da 7a Lista de Exercícios de Fixação
   

1.27.1 Exercícios

1. Resolva os exercícios D,E,G da 7a Lista de Exercícios de Fixação
   

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