Programação das aulas

Março

Abril

Maio

Junho

• 1 de junho (Aula 19):
  • Filas de prioridade
  Leitura recomendada: CLRS, sec 6.1 a 6.3.
  Exercício 1: Escreva a função sobeheap, que recebe como parâmetros H, n e i, onde H[1..n] é um heap a menos da posição i, cujo valor da chave foi alterado para um valor maior que o anterior.
  Exercício 2: Escreva a função desceheap, que recebe como parâmetros H, n e i, onde H[1..n] é um heap a menos da posição i, cujo valor da chave foi alterado para um valor menor que o anterior.
  Exercício 3: Escreva a função alterachave, que recebe como parâmetros H, n, i e x, onde H[1..n] é um heap, e altera o valor da chave da posição i para x, ajustando o heap se necessário.
  Exercício 4: Escreva a função remove, que recebe como parâmetros H, n e i, onde H[1..n] é um heap, e remove a chave da posição i do heap, ajustando-o conforme o necessário.

• 5 de junho (Aula 20):
  • Árvores de sufixo
  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 22):
  • Árvores de sufixo
  Leitura recomendada: Cap 7 do livro do Gustfield, que contém uma série de aplicações de árvore de sufixos.
  Exercício 1: Dada uma cadeia de caracteres S[1..m], use o algoritmo de busca visto em aula para construir a árvore de sufixos para S em tempo O(m^2).
  Exercício 2: Dadas duas cadeias de caracteres, S[1..m] e T[1..n], determinar uma cadeia de caracteres X[1..t] de comprimento máximo que é subcadeia tanto de S quanto de T. Descreva um algoritmo que resolva esse problema em tempo O(m+n).
  Exercício 3: Dada uma cadeia de caracteres S[1..m] que representa uma cadeia circular, determine a linearização de S que é mínima lexicograficamente. Descreva um algoritmo que resolva esse problema em tempo O(m).

• 12 de junho (Aula 23):
  • Tabelas de espalhamento
  • Lista 6 (árvores de sufixo e tabelas de espalhamento) [ps] [pdf]
  Leitura recomendada: CLRS, sec 11.1, 11.2 e boa parte da 11.3.

• 15 de junho:
  • Não haverá aula (Corpus Christi)

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

• 22 de junho (Aula 24):
  • 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.