Estruturas de Dados e Algoritmos

horários das aulas: terças e quintas de 9:00 às 11:00h na sala 217

Ementa da disciplina

• Introdução: revisão de C, recursividade e complexidade de algoritmos;
• Listas lineares com alocações sequencial e encadeada;
• pilhas e filas com alocações sequencial e encadeada;
• Árvores: árvores binárias e árvores balanceadas;
• Heaps; e
• Tabelas hash.

Critério de avaliação

Literatura básica

• W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus.
• T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill.
• J. Szwarcfiter e L. Markenzon, Estruturas de Dados e Algoritmos, LTC.
• B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Campus.

Aulas ministradas

• 13/08/2019

  • Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada;
  • Introdução a linguagem C: tipos e variáveis; e
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos.
  • Datas importantes:
    • P1: 12/09/2019
    • P2: 24/10/2019
    • P3: 26/11/2019
    • Entrega de todas as notas da disciplina: 28/11/2019

• 15/08/2019

  • Precedência de operadores;
  • Operadores: binários, ternário e sizeof(tipo);
  • Entrada e saída básicas (scanf e printf);
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break e continue;
  • Seleção com switch-case-default;
  • Exemplo: escrita de um programa que "infinitamente" lia uma sequência de tamanho n e retornava o tamanho da maior subsequência estritamente crescente. Esse programa parava quando n ≤ 0; e
  • Exercícios.

• 20/08/2019 (aula de exercícios devido ao problema na Ponte Rio-Niterói)

  • Escreva um programa que "infinitamente":
    • leia uma sequência de tamanho n e retorne o número de vezes que essa sequência deixou de ser estritamente crescente. Esse programa pára quando n ≤ 0;
    • leia dois números x e y, e retorne o MDC entre eles. Esse programa pára quando x,y ≤ 1;
    • leia um número n, e retorne o n-ésimo termo da sequência de Fibonacci, sabendo-se que fib(0) = 1 e fib(1) = 1. Esse programa pára quando n < 0; e
    • leia um número n, e retorne todos os divisores dele. Esse programa pára quando n < 2.

• 22/08/2019

  • Funções e pilha de execução;
  • Ponteiros;
  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Exemplo de aplicação: versão iterativa do algoritmo de ordenação selection sort; e
  • Exercícios.

• 27/08/2019

  • Implementação das versões iterativa e recursiva do algoritmo de ordenação selection sort;
  • Ordenação de vetor usando o algoritmo de ordenação quicksort, e apresentação da função qsort presente em stdlib.h;
  • Implementação das versões iterativa e recursiva do algoritmo de busca binária; e
  • Alocação dinâmica de vetores usando malloc, realloc e free da biblioteca stdlib.h, com exemplos de uso.

• 29/08/2019

  • Exemplo de aplicação: ordenação dos dados de um vetor, mantendo a ordem do vetor original;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Apresentação de funções da bilioteca string.h: implementação de versões iterativa e recursiva de strlen e strcmp;
  • Declaração de matrizes;
  • Alocação dinâmica de matrizes;
  • Passagem de matriz como parâmetro de entrada de funções;
  • Exemplo de aplicação: função que retorna a matriz transposta; e
  • Exercícios.

• 03/09/2019

  • Exemplo de aplicação de matrizes: função que verifica a simetria da matriz recebida como parâmetro de entrada, e retorna ou a matriz transposta, ou a matriz triangular inferior;
  • Tipo estrutura;
  • Variáveis do tipo estrutura;
  • Ponteiros para o tipo estrutura; e
  • Exercícios.

• 05/09/2019

  • Motivação para o uso de listas;
  • Definição de listas;
  • Operações básicas que só possuem uma versão iterativa: (a) inicialização e (b) inserção de um elemento no início da lista;
  • Operações básicas que possuem versões iterativa e recursiva: (a) inserção de um elemento no fim de uma lista, (b) inserção de um elemento na lista ordenada e (c) impressões, nas ordens direta e inversa, da lista; e
  • Exercícios.

• 10/09/2019

  • Outras operações básicas que possuem versões iterativa e recursiva: (a) liberação da lista, (b) algumas remoções em lista e (c) busca da primeira ocorrência de um elemento;
  • Motivação para o uso de listas circulares;
  • Definição de listas circulares; e
  • Operações básicas: (a) inicialização e (b) inserções mais barata e mais cara, em termos de complexidade, de um elemento na lista.

• 12/09/2019 (primeira prova)

• 17/09/2019

  • Operações básicas em listas circulares, com versões iterativas e recursivas: (a) busca de um elemento, (b) impressão da lista, (c) liberação da lista e (d) retirada da primeira ocorrência de um elemento nesta lista;
  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas; e
  • Operações básicas: (a) inicialização, (b) busca de um elemento, (c) inserção de um elemento no início da lista, (d) inserção ordenada na lista duplamente encadeada, e (e) retirada da primeira ocorrência de um elemento na lista.

• 19/09/2019

  • Motivação para o uso de listas simplesmente encadeadas com descritores;
  • Definição desse tipo de lista;
  • Operações básicas: (a) inicialização e (b) inserção de um elemento no início da lista, (c) inserção de um elemento na lista ordenada, (d) impressão da lista e (e) destruição da lista;
  • Motivação para o uso de pilhas;
  • Exemplo de uso: ordenação da própria pilha passada como parâmetro de entrada;
  • Implementação de pilhas com vetores e listas;
  • Operações básicas: (a) inicialização, (b) retirada de um elemento do topo da pilha - a operação pop, (c) inserção de um elemento no topo da pilha - a operação push, (d) teste se a pilha está vazia e (e) destruição da pilha;
  • Motivação para o uso de filas; e
  • Exercício: implementação da função que copia uma fila.

• 24/09/2019

  • Implementação de filas com vetores e listas;
  • Operações básicas: (a) inicialização, (b) inserção de um elemento no fim da fila, (c) teste se a fila está vazia, (d) retirada de um elemento do ínicio da fila e (e) destruição da fila;
  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Duas operações básicas: a inicialização da árvore e a criação da árvore recebendo, como parâmetros de entrada, a raiz e as subárvores esquerda e direita;
  • Exemplo: descoberta do maior elemento da árvore; e
  • Exercícios.

• 26/09/2019 (revisão da nota da primeira prova, com o fornecimento de um gabarito de respostas)

• 01/10/2019

  • Percorrimento em árvores binárias: pré-ordem, pós-ordem, simétrica e largura;
  • Operações básicas de árvores binárias: (a) impressão (pré-ordem, pós-ordem, simétrica e largura), (b) liberação de árvores binárias e (c) busca de uma informação na árvore;
  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca;
  • Operações básicas (além das demais supracitadas): (a) busca e (b) inserção;
  • Exemplos de uso: retornar o maior elemento da árvore binária de busca e verificar se uma árvore binária é uma binária de busca; e
  • Exercícios.

• 03/10/2019

  • Remoção de um elemento de uma árvore binária de busca;
  • Motivação para o uso de árvores AVL e AVP;
  • Definição de árvores binárias AVL;
  • Ideia das operações básicas: rotação a esquerda, rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda, inserção e de remoção de nós em AVL;
  • Exemplos de inserções e retiradas em AVL; e
  • Exercícios.

• 08/10/2019

  • Código que mostra o funcionamento da AVL;
  • Motivação para o uso de árvores B;
  • Definição de árvores B; e
  • Implementação da operação de criação de um nó de árvore B.

• 10/10/2019

  • Implementação de algumas funções básicas, incluindo a impressão, a busca de um elemento na árvore e a liberação de toda estrutura alocada em cada nó; e
  • Exemplos de código implementados: encontro da maior chave e retorno de uma lista com todos os elementos maiores que uma chave k.

• 17/10/2019

  • Ideia da operação de inserção, bem como das operações de divisão e de inserção em um nó não completo usadas no código; e
  • Explicação dos casos necessários (1, 2A, 2B, 2C, 3A e 3B) para o desenvolvimento do algoritmo de remoção em árvores B, ilustrando-os com exemplos.

• 22/10/2019 (aula de dúvidas para a segunda prova)

• 24/10/2019 (segunda prova)

• 29/10/2019

  • Revisão dos casos necessários (1, 2A, 2B, 2C, 3A e 3B) do algoritmo de remoção em árvores B, ilustrando-os com exemplos;
  • Código da árvore B;
  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Discussão de algumas operações em árvores B⁺:
    • Busca de uma chave; e
    • Tratamento das divisões de nós requeridas na operação de inserção, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas.

• 31/10/2019

  • Discussão do código da árvore B e da árvore B⁺;
  • Ilustrações de inserção em árvores B⁺;
  • Soluções encontradas para lidar com os casos 3A e 3B da operação de retirada, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas;
  • Motivação para o aprendizado de heaps;
  • Operações básicas de heaps:
    • int pai (int indice);
    • int esquerda (int indice);
    • int direita (int indice); e
    • void max_heapfy (int* heap, int n, int indice).

• 05/11/2019

  • Operação básica de heap: void build_maxheap (int* heap, int n);
  • Algoritmo de ordenação heapsort;
  • Motivação para o uso de tabelas hash (ou tabelas de dispersão);
  • Definição de tabelas hash;
  • Características ideais das funções de hash: ser facilmente computável, ser determinística, seguir a distribuição uniforme e produzir um número baixo de colisões; e
  • Exemplo de função de hash - método da divisão.

• 07/11/2019 (revisão da nota da segunda prova, com o fornecimento de um gabarito de respostas)

• 12/11/2019

  • Ideia dos três tipos de tratamento de colisões em memória principal: (a) por endereçamento aberto, (b) por encadeamento externo e (c) por encadeamento interno;
  • Definição do tratamento de colisões em tabelas hash armazenadas em memória principal - encadeamento externo; e
  • Implementações das operações para esse tiṕo de tratamento de colisão: (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera.

• 14/11/2019

  • Revisão para a terceira prova: (a) geração de uma árvore binária de busca balanceada usando a operação de criação, dados um vetor ordenado e seu tamanho, e (b) retirada de pares de uma árvore binária.

• 19/11/2019

  • Revisão para a terceira prova: (a) inserções e retiradas em árvores B e B⁺, (b) teste se uma sub-árvore esquerda de uma árvore binária é sempre folha, (c) contagem do número de chaves em árvores B e B⁺, e (d) implementação da operação void min_heapfy (int* heap, int n, int indice) em um heap binário.

• 26/11/2019 (terceira prova)

• 05/12/2019 (revisão das notas da terceira prova e divulgação das médias finais)