Turma A Local e horário das aulas: AT9 214 ter 16h-18h / AT9 199 qui 16h-18h. Notas Prova 1:PDF. Notas Prova 2:PDF. Notas Sub:PDF. Notas Trabalhos:PDF. Notas Finais:PDF.
Atendimentos Local e horário: G.08 do DC ter 13h-14h. Local e horários (monitor): Sala de Reuniões 2 do DC seg 08h-10h, ter 14h-16h, qui 10h-12h.
Trabalhos Práticos
Primeiro Trabalho Prático
Instruções disponíveis na página da disciplina no run codes.
Segundo Trabalho Prático
Instruções disponíveis na página da disciplina no run codes.
Terceiro Trabalho Prático
Instruções disponíveis na página da disciplina no run codes.
Quarto Trabalho Prático
Instruções disponíveis na página da disciplina no run codes.
Tópicos das Aulas
Apresentação, estruturas de dados, tabelas de símbolos e hash tables Notas de aula:PDF. Bibliografia: Tópicos Leiaute, Documentação e Hashing do Projeto de Algoritmos (em C), Seções 12.1 e 12.2 do Algorithms Illuminated, Part 2, Tópico Tabelas de símbolos das notas de aula do prof. Paulo Feofiloff. Material complementar: Vídeo aulas do prof. Tim Roughgarden 12 1, 14 1.
Implementação de hash tables Notas de aula:PDF. Códigos da aula:hashLista.c, hashSondagem.c. Bibliografia: Tópico Hashing do Projeto de Algoritmos (em C), Seções 12.3 e 12.4 do Algorithms Illuminated, Part 2, Capítulo 10 do Estruturas de Dados e Técnicas de Programação, Tópico Hashing das notas de aula do prof. Paulo Feofiloff. Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 23 e vídeo aulas do prof. Tim Roughgarden 14 2, 14 3.
Vetores ordenados e árvores de busca Notas de aula:PDF. Bibliografia: Seções 11.1, 11.2 e 11.3 do Algorithms Illuminated, Part 2, Tópicos Árvores Binárias e Árvores Binárias de Busca do Projeto de Algoritmos (em C), Tópicos TSs ordenadas 1 e 2, Árvores binárias de busca 1 e 2 das notas de aula do prof. Paulo Feofiloff. Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 25 e vídeo aulas do prof. Tim Roughgarden 13 1, 13 2, 13 3.
Árvores binárias de busca balanceadas e rotações Notas de aula:PDF. Bibliografia: Seções 11.3 e 11.4 do Algorithms Illuminated, Part 2. Material complementar: Vídeo aulas do prof. Tim Roughgarden 13 5.
Skip lists Notas de aula:PDF. Bibliografia: Seção 13.5 do Algorithms in C++, Parts 1-4, Tópico Números aleatórios do Projeto de Algoritmos (em C).
Projeto e análise de algoritmos, segmento de soma máxima Notas de aula:PDF. Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 16.
Heap e ordenação por seleção eficiente (heapsort) Notas de aula:PDF. Bibliografia: Tópico Heapsort do Projeto de Algoritmos (em C), Seção 13.3 do Estruturas de Dados e Técnicas de Programação. Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 21 e vídeo aulas do prof. Tim Roughgarden 12 2 e 12 3.
Problema da seleção Notas de aula:PDF. Bibliografia: Seções 6.1 e 6.2 do Algorithms Illuminated, Part 1, Seções 9.1 e 9.2 do Introduction to Algorithms, Tópico Mediana e i-ésimo menor elemento das notas de aula do prof. Paulo Feofiloff, Tópico Números aleatórios do Projeto de Algoritmos (em C). Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 20 e vídeo aulas do prof. Tim Roughgarden 8 1 e 8 2.
Problema da contagem de inversões, limitante inferior para ordenação baseada em comparações Notas de aula:PDF. Bibliografia: Seções 3.2 e 5.6 do Algorithms Illuminated, Part 1, Seção 8.1 do Introduction to Algorithms. Material complementar: Vídeo aulas do prof. Tim Roughgarden 3 1, 3 2 e 8 6.
Ordenação por contagem (counting sort) Notas de aula:PDF. Bibliografia: Tópico Ordenação digital do Projeto de Algoritmos (em C), Seção 6.10 do Algorithms in C++, Parts 1-4, Seção 8.2 do Introduction to Algorithms.
Radix sort e bucket sort Notas de aula:PDF. Bibliografia: Tópico Ordenação digital do Projeto de Algoritmos (em C), Capítulo 10 do Algorithms in C++, Parts 1-4, Seções 8.3 e 8.4 do Introduction to Algorithms.
Busca de palavras em um texto, algoritmo de Boyer-Moore (bad character heuristic) Notas de aula:PDF. Bibliografia: Tópico Busca de palavras em um texto do Projeto de Algoritmos (em C). Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 22.
Busca de palavras em um texto, algoritmo de Boyer-Moore (good suffix heuristic) Notas de aula:PDF. Bibliografia: Tópico Busca de palavras em um texto do Projeto de Algoritmos (em C). Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 22.
Árvores de Busca Digital Notas de aula:PDF. Bibliografia: Seção 15.1 do Algorithms in C++, Parts 1-4.
Busca em largura, cálculo de distâncias Notas de aula:PDF. Bibliografia: Tópicos Caminhos mínimos, Busca em largura (BFS), Algoritmo de caminhos mínimos das notas de aula do prof. Paulo Feofiloff, Seção 8.2 do Algorithms Illuminated, Part 2. Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 2, 10 3.
Busca em profundidade, conectividade Notas de aula:PDF. Bibliografia: Tópicos Busca em profundidade (DFS), Componentes conexas das notas de aula do prof. Paulo Feofiloff, Seções 8.4 e 8.3 do Algorithms Illuminated, Part 2. Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 5, 10 4.
Ordenação topológica, DFS, DAGs aleatórios Notas de aula:PDF. Bibliografia: Tópicos Florestas DFS, Ciclos versus dags, DFS e pós-ordem das notas de aula do prof. Paulo Feofiloff, Seção 8.5 do Algorithms Illuminated, Part 2. Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 6.
Caminhos mínimos ponderados, grafos sem custos negativos e algoritmo de Dijkstra Notas de aula:PDF. Bibliografia: Tópico Algoritmo de Dijkstra, Seções 9.3, 9.4, 10.4 e 10.5 do Algorithms Illuminated, Part 2. Material complementar: Vídeo aulas do prof. Tim Roughgarden 11 3, 11 4, 12 2.
