Horário: 3as, das 13h às 17h.
Início: 13 de setembro de 2016.
Repositório do código criado em sala de aula:
https://github.com/vigusmao/OrgDados2_2016_2
Ementa:
- Interpolation search;
- Range queries;
- Cartesian trees;
- Segment trees;
- Lowest Common Ancestor;
- Disjoint sets (Union/Find);
- String matching (Rabin-Karp, KMP);
- Treaps;
- Interval trees;
- Fenwick trees (binary indexed trees);
- SQRT-decomposition;
- Bloom filters; - Conjunto independente máximo em árvores; - classes P e NP; problemas NP-difíceis; domínio restrito.
Primeiro trabalho:
Busca interpolada.
Implemente o algoritmo da busca interpolada e compare seu desempenho com o algoritmo de busca binária, para vários tipos de entradas distintas.
Prazo: 27 de setembro, às 23:59. Entrega por e-mail.
Segundo trabalho:
Disjoint sets.
Implemente o algoritmo clássico para conjuntos disjuntos, com e sem union by rank, com e sem path compression. Compare os desempenhos.
Prazo: 26 de outubro, às 23:59. Entrega por e-mail.
Terceiro trabalho:
Retângulo de palavras: dada uma lista de palavras válidas, encontre o maior retângulo de caracteres que exiba exatamente uma palavra válida em cada linha (ocupando toda a linha) e em cada coluna (ocupando toda a coluna).
Estenda a solução do problema do retângulo de palavras (código no github), ou implemente from scratch.
Observe que:
1) Sem a otimização de podar a busca tão logo seja inserida uma palavra que gere prefixos invalidos, o programa rodaria "para sempre".
2) Fazendo a otimização (poda), mas implementando a verificação dos prefixos através de uma varredura de toda a lista de palavras do tamanho desejado para testar se alguma delas possui aquele prefixo, o programa passa a rodar em tempo razoável.
3) Implementando a verificação dos prefixos usando tries, o programa roda instantaneamente. Sobre essa parte, nada foi feito em sala de aula.
Prazo: 6 de dezembro, às 23:59. Entrega por e-mail.
Quarto trabalho:
Implementação de algoritmo de pattern matching com filtros por linhas. Dado um arquivo-texto de entrada com t linhas de no máximo n caracteres cada, o programa deve pre-processar cada linha de forma a obter sua assinatura baseada nas k-uplas de caracteres consecutivos presentes na linha. Cada k-upla é mapeada a b inteiros de 0 a m-1, para algum b ≥ 0, por funções hash escolhidas por você A assinatura consiste em uma palavra de m bits, onde os bits 1 são aqueles que correspondem às imagens das k-uplas da linha. Você deve tentar valores diferentes de k, m e b, e relatar que valores apresentaram melhores resultados para textos grandes aleatórios (você pode também usar algo como o Lorem ipsum, por exemplo).
Prazo: domingo, 18 de dezembro, às 23:59. Entrega por e-mail.
Bibliografia sugerida
| File Organization and Processing | Introduction to Algorithms | ||
| (Alan L. Tharp) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
13/09
Introdução: Tópicos Especiais em Como Derrotar o Código do Próximo. :-)
Ordenando uma lista imensa. Que perguntas são relevantes? Exemplo de ordenação possível em tempo linear: Count Sort.
Interseção de listas: método ingênuo; pré-ordenando e usando busca binária; usando hash sets.
Busca Interpolada (Interpolation Search).
20/09
Range Query: soma, mínimo. Cartesian tree.
Implementação dos algoritmos para interseção de listas: código em Python disponível aqui.
27/09
Segment trees. Método generalizável para problemas de Range Queries. Exemplos: mínimo, média, máxima subsequência parentizada corretamente.
04/10
Lowest Common Ancestor. Algoritmo linear (offline) de Tarjan.
Disjoint sets (Union/Find).
11/10
String searching. Rabin-Karp, Knuth-Morris-Pratt.Bloom filters.
25/10
Complexidade do KMP. Indexação de documentos via Bloom filters usando tuplas de caracteres contíguos como elementos.Árvore binária de busca ótima.
01/11
Classes P e NP. Problemas NP-difíceis. Domínio restrito.Ex.: conjunto independente máximo em árvores (o problema da festa da empresa).
08/11
Tries. O problema do retângulo de palavras.22/11
Fenwick trees. Treaps.06/12
Introdução a algoritmos aproximativos.
