Algoritmos e Estruturas de Dados 2

Turma A - 1s2025

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

• Comentários do Prof. Tim Roughgarden da Stanford University sobre:
  Por que estudar algoritmos?
  O que se ganha em um curso de algoritmos?
  
  
• Conceitos matemáticos úteis para entender algoritmos:
  Probabilidade e análise combinatória
  Séries (progressões aritméticas e geométricas)
  
  
• Cronograma previsto
  Tabela: PDF.
  
  
• Critérios de Avaliação e Plágio
  Texto: PDF.
  
  
• Turma A
  Local e horário das aulas: AT9 215 seg 16h-18h / AT9 215 qui 16h-18h.
  
  

Tópicos das Aulas

1. Apresentação, estruturas de dados, problema 2-sum
   Vídeos da aula 01: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópicos Leiaute e Documentação do Projeto de Algoritmos (em C).
   Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 1, 12 1.
   
2. Ordenação por inserção (insertionSort) e ordenação por seleção (selectionSort)
   Vídeos da aula 20 (emprestado de AED1): Playlist.
   Vídeos da aula 21 (emprestado de AED1): Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópicos Ordenação: algoritmos elementares do Projeto de Algoritmos (em C), Seções 13.1 e 13.2 do Estruturas de Dados e Técnicas de Programação.
   Bibliografia: Tópico Ordenação: algoritmos elementares 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 18.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 18.
   
3. Filas de prioridade (heap) e Ordenação por seleção eficiente (heapSort)
   Vídeos da aula 19 (emprestado de AED1): Playlist.
   Vídeos da aula 22 (emprestado de AED1): Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópico Heapsort do Projeto de Algoritmos (em C), Seção 8.4 do Estruturas de Dados e Técnicas de Programação.
   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 3.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 21 e vídeo aulas do prof. Tim Roughgarden 12 2.
   
4. Revisão de recursão e de programação com retrocesso (backtracking)
   Vídeos da aula 02 (emprestado de AED1): Playlist.
   Vídeos da aula 05 (emprestado de AED1): Playlist.
   Vídeos da aula 04 (emprestado de AED1): Playlist.
   Notas de aula: PDF.
   Bibliografia: Seção 5.1 do Estruturas de Dados e Técnicas de Programação.
   Bibliografia: Seção 9.1 do Algorithms.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 01, Aula 03.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 24.
   
5. 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.
   
6. 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.
   
7. 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.
   
8. Limitante inferior para ordenação baseada em comparações e Ordenação por contagem (countingSort)
   Vídeos da aula 14: Playlist.
   Notas de aula: PDF1 e PDF2.
   Bibliografia: Seções 5.6 do Algorithms Illuminated, Part 1, Seções 8.1 e 8.4 do Introduction to Algorithms; 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.
   Material complementar: Vídeo aulas do prof. Tim Roughgarden 8 6.
   
9. 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.
   
10. Revisão, Exercícios e Dúvidas
    Exercícios recomendados: Ordenação, Ordenação digital, busca de palavras, tries.
    
11. Prova 1
    
12. Revisão de busca sequencial e binária em vetores, tabelas de símbolos em vetores ordenados
    Vídeos da aula 03 (emprestado de AED1): Playlist.
    Vídeos da aula 23 (emprestado de AED1): Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Busca em vetor ordenado 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.
    Bibliografia: Seções 11.1 e 11.2 do Algorithms Illuminated, Part 2, Tópicos TSs ordenadas 1 e 2 das notas de aula do prof. Paulo Feofiloff, Tópico Á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 17.
    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.
    
13. Á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.
    
14. 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.
    
15. Árvores AVL: altura máxima e remoção, crescimento de funções
    Vídeos da aula 04: Playlist.
    Vídeos da aula bônus sobre Skip lists: Playlist.
    Vídeos da aula bônus sobre Árvores Rubro-Negras: Playlist.
    Notas de aula: PDF, PDF_Skip_Lists, PDF_Rubro-Negra.
    Bibliografia: Seção 8.1 do Estruturas de Dados e Técnicas de Programação, Seção 13.5 do Algorithms in C++, Parts 1-4, Tópico Números aleatórios do Projeto de Algoritmos (em C).
    
16. 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.
    
17. 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.
    
18. Árvores de Busca Digital
    Vídeos da aula 16: Playlist.
    Vídeos da aula bônus sobre Tries: Playlist.
    Vídeos da aula bônus sobre PATRICIA Tries: Playlist.
    Notas de aula: PDF, PDF_Tries, PDF_PATRICIA_Tries.
    Bibliografia: Seção 15.1 do Algorithms in C++, Parts 1-4.
    
19. Revisão, Exercícios e Dúvidas
    Vídeos da aula 12 bônus: Playlist.
    Exercícios recomendados: Árvores binárias de busca, Árvores AVL e rubro-negras, Hash tables.
    
20. Prova 2
    
21. Grafos: tipos, implementação e construção aleatória
    Vídeos da aula 19: 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.
    
22. Busca em profundidade, conectividade
    Vídeos da aula 20: 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.
    
23. Ordenação topológica, DFS, DAGs aleatórios e embaralhamento de Knuth
    Vídeos da aula 21: 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.
    
24. Componentes fortemente conexos, algoritmo de Kosaraju
    Vídeos da aula 22: 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.
    
25. Busca em largura, caminhos mínimos em grafos não ponderados
    Vídeos da aula 23: 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.
    
26. Caminhos mínimos ponderados em grafos sem custos negativos e algoritmo de Dijkstra
    Vídeos da aula 24: 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.
    
27. Caminhos mínimos ponderados e implementação eficiente do algoritmo de Dijkstra
    Vídeos da aula 25: 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.
    
28. Revisão, Exercícios e Dúvidas
    Vídeos da aula 29 bônus: Playlist.
    Exercícios recomendados: Representação de grafos, Busca em profundidade, Busca em largura, caminhos mínimos e Dijkstra.
    
29. Prova 3
    

Playlists de Ofertas Anteriores deste e de Outros Cursos

• Algoritmos e Estruturas de Dados 1 (2022): Playlist.
• Algoritmos e Estruturas de Dados 2 (2021): Playlist.
• AED2 2022: Playlist.
• AED2 2023: Playlist.
• Projeto e Análise de Algoritmos (2021): Playlist.
• PAA 2023: Playlist.
• Introdução à Otimização Combinatória Aplicada (2020): Playlist.

Códigos usados nas Aulas

• Cursos-Professor-Mario/AED2-2024s1
  

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

• Tim Roughgarden. Algorithms Illuminated, Part 2: Graph Algorithms and Data Structures. Soundlikeyourself Publishing, LLC, 2018.
• Tim Roughgarden. Algorithms Illuminated, Part 1: The Basics. Soundlikeyourself Publishing, LLC, 2017.
• R. Sedgewick. Algorithms in C++, Parts 1-4: fundamentals, data structures, sorting, searching. 3rd. ed., Boston: Addison - Wesley, 1998.
• R. Sedgewick. Algorithms in C++, Part 5: graph algorithms. 3rd. ed., Boston: Addison-Wesley, 2001.
• Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
• Notas de aula sobre estruturas de dados do prof. Paulo Feofiloff, do IME-USP.
• Notas de aula sobre análise de algoritmos do prof. Paulo Feofiloff, do IME-USP.
• Paulo Feofiloff. Algoritmos em Linguagem C. Elsevier, 2009. Link para site Projeto de Algoritmos (em C) do mesmo autor com material do livro
• José Coelho de Pina Junior. MAC0122 Princípios de Desenvolvimento de Algoritmos. IME-USP, 2014. SLIDES
• Nivio Ziviani. Projetos de algoritmos: com implementações em Java e C++. 2a ed., São Paulo: Cengage Learning, 2011.
• Adam Drozdek. Estruturas de dados e algoritmos em C++. São Paulo: Cengage Learning, 2010.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd. ed., MIT Press, 2009.
• Lucchesi, C.L., Kowaltowski, T.. Estruturas de Dados e Técnicas de Programação. Versão 1.12, 2004. PDF
• Gomide A.; Stolfi J.. Elementos de Matemática Discreta para Computação. PDF