Para voltar à página raíz clique aqui.

Algoritmos e Estruturas de Dados 2

Turmas A e B - 1s2022

Informações do Professor

Nome: Mário César San Felice
Sala: G.08 do Departamento de Computação
Email: [ meu último nome ] (at) ufscar.br

Informações do Curso

Trabalhos Práticos

Tópicos das Aulas

Aula 01 - Apresentação, estruturas de dados, tabelas de símbolos
Vídeos da aula 01: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Leiaute e Documentação do Projeto de Algoritmos (em C), Tópicos Tabelas de símbolos e TS implementada com busca binária das notas de aula do prof. Paulo Feofiloff, Seção 12.1 do Algorithms in C++, Parts 1-4.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 1, 12 1.

Aula 02 - Árvores binárias de busca, altura e balanceamento
Vídeos da aula 02: Playlist.
Notas de aula: PDF.
Bibliografia: Seções 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).
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.

Aula 03 - Rotações e árvores AVL: definição e inserção
Vídeos da aula 03: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 11.4 do Algorithms Illuminated, Part 2, Seção 8.1 do Estruturas de Dados e Técnicas de Programação.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 13 5.

Aula 04 - Árvores AVL: altura máxima e remoção
Vídeos da aula 04: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 8.1 do Estruturas de Dados e Técnicas de Programação.

Aula 05 - Árvores rubro-negras
Vídeos da aula 05: Playlist.
Notas de aula: PDF.
Bibliografia: Tópico BSTs rubro-negras das notas de aula do prof. Paulo Feofiloff.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 13 4, 13 6.

Aula 06 - Skip lists
Vídeos da aula 06: Playlist.
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).

Aula 07 - Hash tables: espalhamento e colisões
Vídeos da aula 07: Playlist.
Notas de aula: PDF.
Bibliografia: Tópico Hashing do Projeto de Algoritmos (em C), Seções 12.1, 12.2, 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 1, 14 2, 14 3.

Aula 08 - Hash tables: tratando colisões e dimensionando carga
Vídeos da aula 08: Playlist.
Notas de aula: PDF.
Bibliografia: Tópico Hashing do Projeto de Algoritmos (em C), Seções 12.1, 12.2, 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 1, 14 2, 14 3.

Aula 09 - Projeto e análise de algoritmos, segmento de soma máxima
Vídeos da aula 09: Playlist.
Notas de aula: PDF.
Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 16.

Aula 10 - Ordenação por intercalação (mergeSort)
Vídeos da aula 10: Playlist.
Notas de aula: PDF.
Bibliografia: Tópico Mergesort: ordenação por intercalação do Projeto de Algoritmos (em C), Seção 13.4 do Estruturas de Dados e Técnicas de Programação.
Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 19 e vídeo aulas do prof. Tim Roughgarden 1 5, 1 6 e 1 7.

Aula 11 - Problema da separação e quickSort
Vídeos da aula 11: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Quicksort e Números aleatórios do Projeto de Algoritmos (em C), Seção 13.1 do Estruturas de Dados e Técnicas de Programação.
Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 20 e vídeo aulas do prof. Tim Roughgarden 5 1, 5 2, 5 3 e 5 4.

Aula 12 - Problemas da seleção e da contagem de inversões
Vídeos da aula 12: Playlist.
Notas de aula: PDF.
Bibliografia: Seções 3.2, 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 3 1, 3 2, 8 1 e 8 2.

Aula 13 - Limitante inferior para ordenação baseada em comparações e bucketSort
Vídeos da aula 13: Playlist.
Notas de aula: PDF.
Bibliografia: Seções 5.6 do Algorithms Illuminated, Part 1, Seções 8.1 e 8.4 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 8 6.

Aula 14 - Ordenação por contagem (countingSort)
Vídeos da aula 14: Playlist.
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.

Aula 15 - Ordenação por partes (radixSort)
Vídeos da aula 15: Playlist.
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ção 8.3 do Introduction to Algorithms.

Aula 18 - Árvores de Busca Digital
Vídeos da aula 18: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 15.1 do Algorithms in C++, Parts 1-4.

Aula 19 - Tries
Vídeos da aula 19: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 15.2 do Algorithms in C++, Parts 1-4, Tópico Tries (árvores digitais) das notas de aula do prof. Paulo Feofiloff, Seção 8.3 do Estruturas de Dados e Técnicas de Programação.
Material complementar: Slides das aulas do prof. Rafael C. S. Schouery do IC-Unicamp Busca Radix, Árvores Digitais e Tries.

Aula 20 - PATRICIA Tries
Vídeos da aula 20: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 15.3 do Algorithms in C++, Parts 1-4.
Material complementar: Slides das aulas do prof. Rafael C. S. Schouery do IC-Unicamp Busca Radix, Árvores Digitais e Tries.

Aula 21 - Grafos: tipos, implementação e construção aleatória
Vídeos da aula 21: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Estruturas de dados para grafos, Grafos aleatórios das notas de aula do prof. Paulo Feofiloff, Capítulo 7 do Algorithms Illuminated, Part 2.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 9 2.

Aula 22 - Busca em profundidade, conectividade
Vídeos da aula 22: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Acessibilidade, Busca em profundidade (DFS), Componentes conexas das notas de aula do prof. Paulo Feofiloff, Seções 8.1, 8.4 e 8.3 do Algorithms Illuminated, Part 2.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 1, 10 5, 10 4.

Aula 23 - Ordenação topológica, DFS, DAGs aleatórios e embaralhamento de Knuth
Vídeos da aula 23: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Florestas DFS, 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.

Aula 24 - Componentes fortemente conexos, algoritmo de Kosaraju
Vídeos da aula 24: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Componentes fortes, Algoritmo de Kosaraju para componentes fortes, Seção 8.6 do Algorithms Illuminated, Part 2.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 7, 10 8.

Aula 25 - Busca em largura, caminhos mínimos em grafos não ponderados
Vídeos da aula 25: Playlist.
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.

Aula 26 - Caminhos mínimos ponderados em DAGs e em grafos sem custos negativos
Vídeos da aula 26: Playlist.
Notas de aula: PDF.
Bibliografia: Tópicos Caminhos de custo mínimo em dags, Algoritmo de Dijkstra das notas de aula do prof. Paulo Feofiloff, Seção 4.7 do Algorithms, Seções 9.1 e 9.2 do Algorithms Illuminated, Part 2.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 11 1, 11 2.

Aula 27 - Caminhos mínimos ponderados, grafos sem custos negativos e algoritmo de Dijkstra
Vídeos da aula 27: Playlist.
Notas de aula: PDF.
Bibliografia: Tópico Algoritmo de Dijkstra das notas de aula do prof. Paulo Feofiloff, 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.

Aula 16 - 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.

Aula 17 - 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.

Listas de Exercícios

  1. Árvores binárias de busca: PDF.
  2. Árvores AVL e rubro-negras: PDF.
  3. Hash tables: PDF.
  4. Ordenação: PDF.
  5. Ordenação digital, busca de palavras, tries: PDF.
  6. Representação de grafos: PDF.
  7. Busca em profundidade: PDF.
  8. Busca em largura, caminhos mínimos e Dijkstra: PDF.

Bibliografia e Materiais Recomendados

Last Update: 05/06/2022 21:25