Programação das aulas

Sujeito a mudanças...

Fevereiro/Março

Abril

Maio

Junho

• 1 de junho (Aula 22):
  • Tabelas de espalhamento
  Leitura recomendada: CLRS, cap 11. Mas especificamente, as seções 11.1, 11.2 e boa parte da 11.3.

• 6 de junho (Aula 23):
  • Árvores de sufixos
  Leitura recomendada: Cap 5 do livro do Gusfield, um clássico da área de biologia computacional: Algorithms on Strings, Trees, and Sequences - Computer Science and Computacional Biology [QA758 G982a]. No cap 6, você encontra a descrição de dois algoritmos lineares para a construção de uma árvore de sufixos.

• 8 de junho (Aula 24)
  • Árvores de sufixos: busca e aplicações
  • Lista 6 (hashing e árvores de sufixo) [ps.gz] [pdf]
  Leitura recomendada: Cap 7 do livro do Gustfield, que contém uma série de aplicações de árvore de sufixos.

• 13 de junho (Aula 25)
  • Skip lists

• 15 de junho (feriado: Corpus Christi)

• 20 de junho (Aula 26)
  • Skip lists
  • Lista 7 (skip lists) [ps] [pdf]
  Leitura recomendada: sec 8.3 do livro Randomized Algorithms, de Motwani e Raghavan [QA845 M922r] e não lembro qual seção do livro do Sedgewick... No livro do Sedgewick aliás há um estudo comparativo entre árvores de busca e skip lists... Talvez você queira dar uma olhada de curiosidade.

• 22 de junho (Aula 27)
  • Algoritmo de Lempel, Even and Cederbaum
  Leitura sugerida, caso você tenha ficado curioso e queira ler mais coisas sobre o assunto: dê uma olhada na dissertação do Alexandre aqui ou pegue-a na biblioteca [QA758.T N799a]. Para ver o código do teste de planaridade apenas, implementado em C, dê uma olhada aqui.

• 27 de junho
  • O horário dessa aula será usado pelo Prof. Hirata.

• 29 de junho:
  • Prova 3
    Matéria da prova: árvore ótima de busca (CLRS, sec 15.5), B-árvores (CLRS, cap 18), árvores de sufixo (Gusfield, caps 5 e 7), tabelas de espalhamento (CLRS, secs 11.1 a 11.3), filas de prioridade (CLRS, sec 6.5), skip lists (Sedgewick, sec 13.5, e Motwani e Raghavan, sec 8.3).