MAC0323 Algoritmos e Estruturas de Dados II

• [2021-04-13 Tue] Apresentação da disciplina. Um mínimo sobre Java e sobre as bibliotecas de Sedgewick e Wayne
• [2021-04-15 Thu] Tipos. Bag. Tipos iteráveis. Genéricos. Implementação de Bag
• [2021-04-20 Tue] Análise amortizada e tabelas redimensionáveis. Aplicações: sacos, pilhas e filas
• [2021-04-22 Thu] Union-find (tipo-de-dado para partições de conjuntos ou conjuntos disjuntos)
• [2021-04-27 Tue] Comentários sobre os EPs (bibliotecas e performance bugs). Critério de avaliação. Union-find: exemplos de execução e grafos aleatórios. E03. Filas de prioridade com heaps binários. Filas de prioridade com objetos indexados (IndexMinPQ.java). E02
• [2021-04-29 Thu] Imutabilidade (comentários). Event driven simulation. Tabelas de símbolos: recapitulação + \(\varepsilon\)

• [2021-05-04 Tue] Tabelas de símbolos: recapitulação + \(\varepsilon\) (continuação). Implementações elementares e com árvores de busca
• [2021-05-06 Thu] Tabelas de símbolos: implementação com ABBs. Discussão sobre árvores binárias (breve texto). Internal path length e external path length
• [2021-05-11 Tue] Implementação de tabelas de símbolos com árvores balanceadas
• [2021-05-13 Thu] Implementação de tabelas de símbolos com árvores balanceadas (cont.)
• [2021-05-18 Tue] Discussão do E05, Altura e IPL de ABBs e ARNEs. Tabelas de espalhamento (hashing)
• [2021-05-20 Thu] Tabelas de espalhamento (hashing), cont. O paradoxo dos aniversários: veja L. Littleton e R. May, Simplified expectations in the birthday problem, The College Mathematics Journal, 47 (2016), no. 1, 50–55
• [2021-05-25 Tue] Tabelas de espalhamento, cont. Aplicações de tabelas de símbolos (SET.java, LookupCSV.java, FileIndex.java, Concordance.java, SparseVector.java, SparseMatrix.java)
• [2021-05-27 Thu] Tries e TSTs

• [2021-06-01 Tue] Tries e TSTs (cont.)
• [2021-06-03 Thu] Break
• [2021-06-08 Tue] Break
• [2021-06-10 Thu] Compressão de dados: run length encoding; Huffman
• [2021-06-15 Tue] Compressão de dados: Huffman (cont.); LZW
• [2021-06-17 Thu] Compressão de dados: LZW (cont.)
• [2021-06-22 Tue] LZW (comentários finais). Ordenação de strings; vetor de sufixos
• [2021-06-24 Thu] Vetor de sufixos (cont.). LRS (longest repeated substring)
• [2021-06-29 Tue] Grafos: API e implementações; busca em profundidade

• [2021-07-01 Thu] Busca em profundidade (cont.); busca em largura; componentes conexas; Bacon numbers; outros problemas envolvendo grafos
• [2021-07-06 Tue] Grafos dirigidos. Buscas em grafos dirigidos. Ordenação topológica
• [2021-07-08 Thu] Componentes fortes de grafos dirigidos. Caminhos mínimos
• [2021-07-13 Tue] Caminhos mínimos (cont.). Algoritmo de Dijkstra. Caminhos mínimos em DAGs
• [2021-07-15 Thu] Caminhos mínimos em DAGs (cont.). Bellman-Ford. Circuitos negativos e arbitrage
• [2021-07-20 Tue] Busca de padrões em texto. O algoritmo de Knuth, Morris e Pratt (vídeoaula)
• [2021-07-15 Thu] Algoritmo de Boyer e Moore. Algoritmo de Rabin e Karp
• [2021-07-27 Tue] Expressões regulares. Autômatos não-determinísticos
• [2021-07-29 Thu] Autômatos não-determinísticos (cont.). Comentários adicionais. Recomendado: Russ Cox, Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …). Bônus (teste de primalidade)

Página principal de MAC0323, 1o. semestre de 2021