MAC5710 - Estrutura de Dados e sua Manipulação

Cronograma das aulas --- 1o. semestre de 2007

      Su Mo Tu We Th Fr Sa
                   1  2  3
       4  5  6  7  8  9 10
      11 12 13 14 15 16 17
      18 19 20 21 22 23 24
      25 26 27 28 29 30 31

(05/03) : aula 01
• Listas lineares (filas, pilhas e filas duplas)
  Leitura sugerida: páginas 234 a 239 de Knuth, vol.1
• Notas de aula do prof. Siang

(08/03) : aula 02
• Alocação seqüencial de pilhas e filas.
  Leitura sugerida: capítulo 2 de Ziviani, p.240 a 248 de Knuth.
• Exemplo de uso de pilha: cálculo de expressões aritméticas.
• Divulgação do EP1: enunciado
  Uma imagem binária em formato ascii PGM.
  Instruções para entrega dos EPs.
• Divulgação da lista 1: enunciado

(12/03) : aula 03
• Esclarecimento sobre o algoritmo de inserção em Fila, discutida na aula passada.
• Alocação ligada: pilhas e filas usando alocação ligada; alocação e liberação de nós em listas ligadas; alocação sequencial versus alocação ligada.

(15/03) : aula 04
• Listas ligadas com nó-cabeça; listas ligadas circulares; operações de busca, inserção e remoção em listas ligadas; sentinela.
• Referências: Knuth (seção 2.2.4), Szwarcfiter (seção 2.7), entre outros.

(19/03) : aula 05
• Ordenação topológica (Knuth, Seção 2.2.3; Szwarcfiter, seção 2.7.5)

(22/03) : aula 06
• Noções de análise de algoritmos; comportamento assintótico de funções; notações O, Omega e Theta.
• Exemplo de uso de lista ligada: adição de polinômios (Knuth, seção 2.2.4)

(26/03) : aula 07 Data máxima para entrega da lista 1 e do EP1
• Multiplicação de polinômios (Knuth, seção 2.2.4)
• Listas duplamente ligadas
• Representação de matrizes esparsas por listas ligadas (Ziviani)

(29/03) : aula 08
• Observações sobre a representação de matrizes esparsas por listas ligadas vista na aula anterior.
  Referências: Knuth (seção 2.2.6)
• Adição de matrizes esparsas
• Multiplicação de matrizes esparsas

30/03 : Divulgação da lista 2: enunciado

      Su Mo Tu We Th Fr Sa
       1  2  3  4  5  6  7
       8  9 10 11 12 13 14
      15 16 17 18 19 20 21
      22 23 24 25 26 27 28
      29 30

(02/04) : Break 1
(05/04) : Break 1

(03/04) : Divulgacao do EP2: enunciado (para 30/04)

(09/04) : aula 09
• Revisão sobre listas lineares
  Pilhas; Exemplo: Linguagem Postscript
  Filas; discussão sobre a questão da L1 relacionada ao EP1 (pendente)
  Listas ligadas; simples, com e sem nó cabeça, circular, sentinela, duplamente ligadas; Exemplo: problema de Josephus
  Representação de grafos (matriz de adjacência e lista de adjacências).

(12/04) : aula 10
Discussão sobre a lista 1 (Q4, Q2 e Q3)

(16/04) : aula 11 -- Prova 1, data máxima para entrega da L2

(19/04) : aula 12
• Árvores: definição, representação.
  Ref.: Knuth

(23/04) : aula 13
• Árvores binárias; percursos em árvores binárias (pre-ordem, in-ordem e pos-ordem)
  Ref.: Knuth
• Árvores binárias de busca (ABB); operações de busca, mínimo, máximo, predecessor, sucessor, inserção e remoção.
  Ref.: Cormen

(26/04) : aula 14
• Árvores balanceadas (altura é O(log n))
• AVL: definição, operações de rotação
  Ref.: Szwarcfiter, seção 5.3. (PDF com algumas figuras e algoritmos)

(30/04) : Data máxima para entrega do EP2

(01/05) : Break 2
(04/05) : Break 2

(07/05) : aula 15
• AVL: inserção.
  Ref.: Szwarcfiter, seção 5.3.

(10/05) : aula 16
• Árvores rubro-negras: definição; inserção
  Ref.: Cormen et al, cap. 14

12/05 : Divulgacao da lista 3: enunciado

(14/05) : aula 17
• Remoção em árvores rubro-negras

(17/05) : aula 18
• Análise do caso médio em buscas em árvores binárias (comprimento de caminho interno e externo) -- Szwarcfiter

(20/05) : Divulgação do EP3: enunciado (para 21/06)

Dados disponibilizados em 05/06
veja1.pgm.gz
veja2.pgm.gz
veja3.pgm.gz
veja4.pgm.gz
veja5.pgm.gz


(21/05) : aula 19
• B-Árvores: definição, altura
• Exemplo de inserção em B-árvore
  Ref.: Cormen

(24/05) : aula 20 -- data máxima para entrega da L2
• Inserção em B-árvore (Cormen, Szwarcfiter)
• Remoção em B-árvore (abordagem bottom-up de balanceamento, Szwarcfiter)

(28/05) : aula 21
• Remoção em B-árvore (abordagem top-down de balanceamento, Cormen)
• Comparação, via exemplo, das duas abordagens para remoção.
• Análise de complexidade das operações de busca, inserção e remoção (número de acessos e número de escritas).

(31/05) : aula 22
• B-árvores: variantes (B+-tree, range-query, k-NN query)
• Filas de prioridade: definição; operações de inserção, remoção do máximo e seleção do máximo; implementação via lista linear ordenada e não ordenada; implementação via heap.
• Heap: definição; operações de inserção, remoção, heapify, construção; uso para ordenação (heap_sort).
  Ref.: Cormen, capítulo 7, Szwarcfiter)

(04/06) : Break 3 (não haverá aula)
(04/06): Divulgação da Lista 4: enunciado (para 18/06)

(05/06): Exemplo de dados de entrada para o EP3: ver aqui

(07/06) : Break 3 (não haverá aula)

(11/06) : aula 23
• Tabelas de dispersão: acesso direto, funções de dispersão, colisão, exemplos de funções de dispersão (método da divisão, método da dobra, método da multiplicação, método da análise de dígitos, hashing universal).
  Ref: Cormen (cap. ??) e Szwarcfiter (capítulo ??)

(14/06) : aula 24
• Dúvidas sobre L3
• Tratamento de colisões em tabelas de dispersão (via encadeamento externo ou interno)

(18/06) : aula 25 -- Data limite para entrega da L4
Aula de exercícios

(21/06) : aula 26 -- data máxima para entrega do EP3
• Dúvidas L4
• Tabelas de dispersão: tratamento de colisões via endereçamento aberto

(25/06) -- Prova 2