MAC323 Algoritmos e estruturas de dados II

• [2015-02-24 Tue] Apresentação da disciplina: objetivos e importância. Núcleo: estruturas de dados e algoritmos. Papel importante: abstração. Orientação a objetos; Java. Bibliografia. O sistema Java de S&W. Tópicos administrativos: informações gerais
• [2015-02-26 Thu] Breve introdução ao Java. Páginas da Oracle: http://docs.oracle.com/javase/8/ e http://docs.oracle.com/javase/tutorial/index.html. Anatomia de um programa Java: BinarySearch.java (veja no sandbox). Alguns conceitos: bibliotecas Java, bibliotecas de S&W; main(), métodos (estáticos), métodos da classe e de outras classes. Execução do programa. Java crash course. Capítulos 1 e 2 de S&W, Introduction to programming in Java (veja a página do livro e as transparências).

• [2015-03-03 Tue] Java crash course (continuação). Capítulos 1 e 2 de S&W, Introduction to programming in Java (veja a página do livro e as transparências). Exemplos de uso do StdDraw (imagens e mouse), StdAudio (GuitarHero).
• [2015-03-05 Thu] (Professor não pôde dar aula [estava sem voz…])
• [2015-03-10 Tue] Java crash course (continuação). Métodos estáticos em Java. Bibliotecas e clientes. Exemplos: IFS e Bernoulli. Sumário (de Algorithms, 4th ed.). Elementos de POO. Tipos de dados; abstração; uso: Seção 3.1 de IntroCS.
• [2015-03-12 Thu] Elementos de POO. A classe String. (Veja a observação sobre a mudança da implementação de substring() no OpenJDK Java 7, Update 6, nesta página; veja também este artigo). As classes In e Out de S&W. Implementação de classes: Seções 3.2 e 3.3 de IntroCS. Veja também Algs4th.
• [2015-03-17 Tue] Pilhas e filas (recordação). Implementação com listas ligadas e vetores (implementações com resizing; análise amortizada). Java generics. Uma aplicação de pilhas: avaliação de expressões infixas/pósfixas (algoritmo de Dijkstra).
• [2015-03-19 Thu] Avaliação de expressões infixas/pósfixas (algoritmo de Dijkstra; continuação; versão deluxe). Subtipagem por interfaces (Seção 3.6 de IntroCS; método de Newton). Iteradores. Novamente Newton: bacias de Newton; veja o Creative Exercise 3.2.15 de IntroCS. (Para ler mais sobre subtipagem por herança e por interface, veja, por exemplo, este documento.)
• [2015-03-24 Tue] Análise de algoritmos. Exemplo: o problema do 3SUM. Análise experimental; doubling; modelos matemáticos; modelo de custo; notação "~"; ordem de grandeza (ordem de crescimento); notação \Theta, O e \Omega; recursos envolvidos: tempo e espaço (memória). Busca binária: veja este link.
• [2015-03-26 Thu] 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.
• [2015-03-31 Tue] Semana Santa
• [2015-04-02 Thu] Semana Santa

• [2015-04-07 Tue] Filas de prioridade. API. Uso de chaves que estendem Comparable. Implementações elementares e binary heaps. Exemplo de aplicação: simulações regidas por eventos (event-driven simulation).
• [2015-04-09 Thu] Breve discussão sobre tipos genéricos e bounded type parameters (uso de extends em type parameters: veja, p. ex., este link). Para implementar interfaces, usamos implements; veja, p. ex., a seção do tutorial da Oracle. (Para os que querem saber mais: veja a aula Interfaces e herança do tutorial.) Filas de prioridade (continuação). Exemplo de aplicação: simulações regidas por eventos (continuação). Se você quer saber o que é null: veja aqui.
• [2015-04-14 Tue] Tipos imutáveis de dados; veja immutability em Algs4th (ou a aula no tutorial). Em particular, veja a implementação da classe Vector. Exemplos de tipos mutáveis: Counter, Accumulator e VisualAccumulator (veja em Algs4th). Um exercício com filas de prioridade: Taxicab numbers. Um exercício de union-find: pior caso de quick-union com pesos. Exercícios de análise de algoritmos (veja a abundância de exercícios em Algs4th). Exercícios de pilhas e filas (idem).
• [2015-04-16 Thu] P1 [p1.pdf | p1b.pdf]
• [2015-04-21 Tue] Feriado
• [2015-04-23 Thu] Tabelas de símbolos. API. Detalhe: testes de igualdade (veja, p. ex., Person.java e Date.java). Implementações elementares (veja em sandbox/2015.04.23). Chaves comparáveis e tabelas de símbolos ordenadas. Operações ordenadas (operações que dependem do fato de as chaves virem de um conjunto totalmente ordenado). Árvores binárias (ABs) e árvores binárias de busca (ABBs). Para uma implementação, veja novamente no sandbox (ou em Algs4th).
• [2015-04-28 Tue] Semana de break
• [2015-04-30 Thu] Semana de break

• [2015-05-05 Tue] Aula cancelada (professor fora do estado)
• [2015-05-07 Thu] Árvores binárias de busca (continuação). O formato de uma ABB e o formato de ABs uniformes [veja estas notas]. Algumas operações ordenadas (rank(), select() e varredura/iteração ordenada). Remoção de ABBs. Árvores binárias de busca balanceadas (ABBB) (introdução). Árvores 2-3. Árvores rubro-negras esquerdistas (introdução).
• [2015-05-12 Tue] LLRB Árvores rubro-negras esquerdistas (continuação). Algoritmo de inserção. Contagem experimental de comparações em execuções de put(): BSTs e LLRBs (classe auxiliar: VisualAccumulator.java).
• [2015-05-14 Thu] Remoção em árvores LLRB: veja Creative problems 3.3.39, 3.3.40 e 3.3.41 de Algs4th. Veja também estas transparências de Sedgewick (veja também esses videos; uma versão posterior/editada dessas transparências estão também disponíveis). Tabelas de espalhamento (hashing). O método hashCode() e funções de espalhamento (hashing); redução módulo M. Resolução de colisões por encadeamento.
• [2015-05-19 Tue] Tabelas de espalhamento (continuação). Resolução de colisões por probing linear. Variantes. Aplicações de tabelas de símbolos. API para SET. Whitelisting e blacklisting. Consulta a dicionários dados por arquivos csv.
• [2015-05-21 Thu] Aplicações de tabelas de símbolos (continuação). Contagem de ocorrências de palavras em texto. Arquivos invertidos: indexação de arquivos, de páginas web, de uma biblioteca digital, criação de índices remissivos de livros. Vetores esparsos.
• [2015-05-26 Tue] Grafos. Introdução. Conceitos básicos: além de Algs4th, veja esta página, mantida pelo prof. Paulo Feofiloff. A API para manipulação de grafos de Algs4th. Representação de grafos no computador. Busca em profundidade.
• [2015-05-28 Thu] Busca em profundidade (continuação). Versão não recursiva de DFS. Busca em largura. Distância em grafos. Componentes conexas e outras aplicações de buscas.

• [2015-06-02 Tue] Semana de break
• [2015-06-04 Thu] Semana de break (Corpus Christi)
• [2015-06-09 Tue] Grafos dirigidos. Introdução. Noções básicas. A API para grafos dirigidos. Busca em profundidade e busca em largura em grafos dirigidos. Um webcrawler primitivo. Ordenação topológica (introdução).
• [2015-06-11 Thu] Ordenação topológica (continuação). Ordenação topológica a partir de busca de profundidade. Componentes fortemente conexas. O algoritmo de Kosaraju e Sharir.
• [2015-06-16 Tue] Grafos dirigidos com pesos. API para arcos com pesos e API para grafos dirigidos com pesos nos arcos. Caminhos mínimos em grafos com pesos. Algoritmo genérico para caminhos mínimos. Algoritmo de Dijkstra.
• [2015-06-18 Thu] P2
• [2015-06-23 Tue] Algoritmo de Dijkstra (continuação). Caminhos mais curtos e mais longos em DAGs. Comentários sobre o caso de grafos com arcos com pesos negativos. Circuitos negativos. Aplicações.
• [2015-06-25 Thu] (PSub fechada cancelada) Expressões regulares. Autômatos determinísticos (DFA) e não-determinísticos (NFA). Simulação de NFAs. Leia sobre regex golf nesse link:

  http://www.explainxkcd.com/wiki/index.php/1313:_Regex_Golf

• [2015-06-30 Tue] Expressões regulares (continuação). Construção de NFAs a partir de expressões regulares. Aplicações de expressões regulares.

• [2015-07-02 Thu] Compressão de dados. Introdução. Run-length encoding. Códigos de Huffman.

Página principal de MAC323, 1o. semestre de 2015