MAC323 Algoritmos e Estruturas de Dados II
[Edição do 1o. Semestre de 2016]
(Página eternamente minimal e em mutação)
Transparências de Sedgewick e Wayne (cópia local)
Documentação de Java
Sinopse das aulas
Fevereiro
- Apresentação da disciplina: objetivos e importância. Núcleo: algoritmos e estruturas de dados. Apoio BCC/grades curriculares: http://bcc.ime.usp.br/principal/index.php?id=grades-curriculares (Nome antigo da disciplina: "Estruturas de dados" (veja popularidade histórica)). Papel importante: abstração. Orientação a objetos; Java. Bibliografia. O sistema Java de S&W. Tópicos administrativos: informações gerais. Paca. Introdução a Java. A biblioteca de entrada e saída de S&W
- Introdução a Java (continuação). A biblioteca de entrada e saída de S&W. Útil: Java programming cheatsheet. Um exemplo estendido: PageRank
Março
- Percolação: o case study do Capítulo 2 de IntroCS
- Palavras finais sobre o case study (percolação). Tipos de dados: uso e implementação
- Tipos de dados: implementação. Um bom tutorial sobre cores: http://www.tomjewett.com/colors
- Tipos de dados: projeto (design). Case study. O problema dos N corpos
- Pilhas e filas (recordação); Java generics, subtipagem por interfaces; iteradores
- Union-find. Versões elementares: quick-find e quick-union. Melhoramento substancial: weighted quick-union (variantes: baseadas em altura e "posto"). Melhoramento adicional: compressão de caminhos; versões: de uma varredura e de duas varreduras (versão iterativa e versão recursiva). Aplicação: percolação 2D.
- Semana Santa (recesso escolar)
- Semana Santa (recesso escolar)
- Tabelas de símbolos. Implementações elementares. Árvores binárias de busca (ABBs)
- Tabelas de símbolos. ABBs (continuação)
Abril
- Árvores 2-3. Árvores rubro-negras esquerdistas, ARNEs (left-leaning red-black trees, LLRBs)
- ARNEs (cont.) Material sobre ARNES (Sedgewick)
- Tabelas de espalhamento/dispersão (tabelas de hashing)
- Tabelas de espalhamento (cont.)
- Semana de break do BCC
- Tiradentes
- Aplicações de tabelas de símbolos. Grafos (introdução)
- Grafos. Busca em profundidade
Maio
- Busca em largura e distância em grafos; componentes conexas
- Grafos dirigidos. Buscas em grafos dirigidos. Ordenação topológica (introdução)
- Ordenação topológica (continuação). Componentes fortes. O algoritmo de Kosaraju e Sharir
- O algoritmo de Kosaraju e Sharir (cont.). Caminhos mais curtos em grafos dirigidos com pesos
- Caminhos mais curtos (cont.). Algoritmo de Dijkstra
- Caminhos mais curtos em DAGs. Caminhos mais longos em DAGs. Aplicações: escalonamento e seam carving. Para seam carving, veja http://www.youtube.com/watch?v=vIFCV2spKtg e https://www.cs.princeton.edu/courses/archive/fall14/cos226/assignments/seamCarving.html. Bellman-Ford; detecção de circuitos negativos e arbitrage
- Semana de break do BCC
- Corpus Christi
- Tries. Tries R-árias. Ternary search tries (TSTs)
Junho
- Ternary search tries (TSTs; cont.). Operações baseadas em caracteres. Busca de padrões (introdução)
- Busca de padrões. (O algoritmo de Knuth, Morris e Pratt) Não foi possível ter aula, por conta do piquete do CAMAT
- Busca de padrões. O algoritmo de Knuth, Morris e Pratt. Aula a ser repetida, por conta do trancaço promovido pelo DCE-USP e pelo SINTUSP
- O algoritmo de Knuth, Morris e Pratt. Para a versão completa de Knuth–Morris–Pratt, veja Seção 3 de http://epubs.siam.org/doi/abs/10.1137/0206024
- O algoritmo de Boyer e Moore e o algoritmo de Rabin e Karp. Expressões regulares
- Expressões regulares e autômatos não-determinísticos (NFAs). Simulação de NFAs. Construção de uma NFA equivalente dada uma expressão regular
- Construção de uma NFA dada uma expressão regular (cont.). Aplicações de expressões regulares. Veja https://docs.oracle.com/javase/tutorial/essential/regex. Compressão de dados
- Compressão de dados. Códigos de Huffman
- Compressão de dados. LZW
Página principal de MAC323, 1o. semestre de 2016