MC202E - Estruturas de Dados

Essa página contém links para slides e vídeos de MC202 - Estruturas de Dados.

Os slides sofrem alterações com o passar do tempo e o link é sempre para a versão mais recente. Assim, os slides mostrados nos vídeos podem não condizer com os slides atuais. Além disso, dependendo do semestre, a ordem de algumas aulas pode mudar em relação a ordem dos vídeos no YouTube. O site será mantido na ordem que as aulas serão ensinadas no respectivo semestre.

Correções nos links e sugestões de outros conteúdos são mais que bem-vindas!

Indíce

1. Aulas
   1. Unidade 1 - Sobre a Disciplina
   2. Unidade 2 - Curso de C - Parte 1
   3. Unidade 3 - Curso de C - Parte 2
   4. Unidade 4 - Curso de C - Parte 3
   5. Unidade 5 - Curso de C - Parte 4
   6. Unidade 6 - Curso de C - Parte 5
   7. Unidade 7 - Curso de C - Parte 6
   8. Unidade 8 - Recursão
   9. Unidade 9 - Noções de Eficiência de Algoritmos
   10. Unidade 10 - Vetores
   11. Unidade 11 - Listas Ligadas
   12. Unidade 12 - Variações de Listas Ligadas
   13. Unidade 13 - Pilha e Fila
   14. Unidade 14 - Aplicações de Pilha
   15. Unidade 15 - Árvores Binárias
   16. Unidade 16 - Árvores Binárias de Busca
   17. Unidade 17 - Árvores Rubro-Negras
   18. Unidade 18 - Filas de Prioridade e Heap
   19. Unidade 19 - Ordenação e Heapsort
   20. Unidade 20 - Mergesort e Quicksort
   21. Unidade 21 - Ordenação em Tempo Linear
   22. Unidade 22 - Hashing
   23. Unidade 23 - Grafos (representação)
   24. Unidade 24 - Grafos (percurso)
   25. Unidade 25 - Grafos (algoritmos)
   26. Unidade 26 - Backtracking
   27. Unidade 27 - Árvores B
   28. Unidade 28 - Gerenciamento de Memória
   29. Unidade 29 - Escolhendo uma ED
2. Tutoriais
3. Tutoriais do Lehilton
4. Links Interessantes
5. Bibliografia

Aulas

Unidade 1 - Sobre a Disciplina

• Slides (handout)

Unidade 2 - Curso de C - Parte 1

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Exercícios Resolvidos

Unidade 3 - Curso de C - Parte 2

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Material relacionado:
  • Why Computers are Bad at Algebra
  • Methods of computing square roots

Unidade 4 - Curso de C - Parte 3

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios

Unidade 5 - Curso de C - Parte 4

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Material relacionado:
  • Wikipedia - Abstract Data Type
  • Capítulo 4 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick

Unidade 6 - Curso de C - Parte 5

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios

Unidade 7 - Curso de C - Parte 6

• Slides (handout)
• Exercícios Resolvidos
• Lista de Exercícios
• Vídeo

Unidade 8 - Recursão

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Material relacionado:
  • Visualgo: Recursion
  • Slides de Recursão em MC102
  • Recursão e algoritmos recursivos
  • Wikipedia - Recursion
  • Wikipedia - Recursion (computer science)

Unidade 9 - Noções de Eficiência de Algoritmos

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Material relacionado
  • Capítulo 2 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulos 1 e 2 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein
  • Avançado: Capítulo 3 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 10 - Vetores

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios

Unidade 11 - Listas Ligadas

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Visualgo - Lista Ligada
• Material relacionado
  • Seção 3.3 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seção 10.2 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 12 - Variações de Listas Ligadas

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Visualgo - Lista Ligada
• What’s a Linked List, Anyway? [Part 1]
• What’s a Linked List, Anyway? [Part 2]
• Material relacionado
  • Seção 3.4 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick

Unidade 13 - Pilha e Fila

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Stacks and Overflows
• To Queue Or Not To Queue
• Material relacionado
  • Seções 4.1 a 4.6 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seção 10.1 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 14 - Aplicações de Pilha

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Material relacionado
  • Seções 4.1 a 4.4 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seção 10.1 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 15 - Árvores Binárias

• Slides (handout)
• Vídeo - Parte 1
• Vídeo - Parte 2
• Exercícios Resolvidos
• Lista de Exercícios
• How To Not Be Stumped By Trees
• Material relacionado
  • Capítulo 12 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 12 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 16 - Árvores Binárias de Busca

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Leaf It Up To Binary Trees
• Material relacionado
  • Capítulo 12 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 12 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 17 - Árvores Rubro-Negras

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Painting Nodes Black With Red-Black Trees
• Material relacionado
  • Capítulo 3 de “Algorithms - Fourth Edition” - R. Sedgewick

Unidade 18 - Filas de Prioridade e Heap

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Visualgo - Heap binário
• Learning to Love Heaps
• Material relacionado
  • Capítulo 9 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 6 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 19 - Ordenação e Heapsort

• Slides (handout)
• Exercícios Resolvidos
• Lista de Exercícios
• Visualgo - Ordenação
• Visualgo - Heap binário
• Learning to Love Heaps
• Sorting Out The Basics Behind Sorting Algorithms
• Exponentially Easy Selection Sort
• Bubbling Up With Bubble Sorts
• Inching Towards Insertion Sort
• Heapify All The Things With Heap Sort
• Algoritmos de Ordenação e Dança:
  • Select-sort with Gypsy folk dance
  • Bubble-sort with Hungarian (“Csángó”) folk dance
  • Insert-sort with Romanian folk dance
  • HEAP-sort with Hungarian (MEZŐSÉGI) folk dance
• Material relacionado
  • Capítulo 6 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 9 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 2 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein
  • Capítulo 6 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 20 - Mergesort e Quicksort

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Visualgo - Ordenação
• Making Sense of Merge Sort [Part 1]
• Making Sense of Merge Sort [Part 2]
• Pivoting To Understand Quicksort [Part 1]
• Pivoting To Understand Quicksort [Part 2]
• Algoritmos de Ordenação e Dança:
  • Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
  • Merge-sort with Transylvanian-saxon (German) folk dance
• Material relacionado
  • Capítulo 7 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 7 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein
  • Capítulo 8 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seção 2.3 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 21 - Ordenação em Tempo Linear

• Slides (handout)
• Vídeo
• Counting Linearly With Counting Sort
• Getting To The Root Of Sorting With Radix Sort

Unidade 22 - Hashing

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Taking Hash Tables Off The Shelf
• Hashing Out Hash Functions
• Material relacionado
  • Capítulo 14 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Capítulo 11 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 23 - Grafos (representação)

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• From Theory To Practice: Representing Graphs
• Material relacionado
  • Capítulo 17 de “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Seção 3.7 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seção 22.1 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 24 - Grafos (percurso)

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Deep Dive Through A Graph: DFS Traversal
• Going Broad In A Graph: BFS Traversal
• Material relacionado
  • Capítulo 18 de “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Seção 5.8 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seções 22.2 e 22.3 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 25 - Grafos (algoritmos)

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Spinning Around In Cycles With Directed Acyclic Graphs
• Finding The Shortest Path, With A Little Help From Dijkstra
• Material relacionado:
  • Seções 19.1 a 19.6, 21.1 e 21.2 de “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Capítulo 14 de “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Seções 22.4 e 24.3 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 26 - Backtracking

• Slides (handout)
• Vídeo
• Exercícios Resolvidos
• Lista de Exercícios
• Material relacionado:
  • Capítulo 12 de “Algoritmos em linguagem C” - Paulo Feofiloff

Unidade 27 - Árvores B

• Slides (handout)
• Vídeo
• Lista de Exercícios
• Busying Oneself With B-Trees
• Material relacionado:
  • Capítulo 18 de “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest e C. Stein

Unidade 28 - Gerenciamento de Memória

• Slides (handout)
• Lista de Exercícios

Unidade 29 - Escolhendo uma ED

• Slides (handout)
• Vídeo (do 2s2017)
• Lista de Exercícios

Tutoriais

• Tutorial de Valgrind
• Tutorial de GDB
• Tutorial de git
• Tutorial para macOS
• Tutorial de Debugging no VSCode

Tutoriais do Lehilton

• gcc
• Valgrind
• gdb
• VSCode
• Indo de Python para C

Links Interessantes

• Visualgo - Animações de algoritmos e estruturas de dados
• Curso Algorithms do KhanAcademy
• An ongoing series of nonverbal algorithm assembly instructions
• A excelente página do Prof. Paulo Feofiloff sobre algoritmos

Bibliografia

A bibliografia principal para o curso é o livro “Algorithms in C - Third Edition” de R. Sedgewick.

Outro livro interessante é “Introduction to Algorithms - Third Edition” de Cormen, Leiserson, Rivest e Stein.

Esta é a bibliografia oficial da disciplina:

• R. Sedgewick, Algorithms in C. Addison-Wesley, 1990.
• T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Algoritmos - Teoria e Prática. Campus, 2002.
• A. V. Aho, J. E. Hopcroft, J. Ullmann. Data Structures and Algorithms. Addison-Wesley, 1983.
• W. Celes, R. Cerqueira, J. L. Rangel. Introdução a Estruturas de Dados. Campus, 2004.
• M. J. Folk e B. Zoellick. File Structures. Addison-Wesley, 1992.
• F. Lorenzi, P. N. de Mattos, T. P. de Carvalho. Estruturas de Dados. Thomson, 2007.
• S. L. Pereira. Estruturas de Dados Fundamentais. Érica, 1996.
• E. M. Reingold e W. J. Hanson, Data Structures. Little-Brown (1983).
• J. L. Szwarcfiter e L. Markenzon. Estruturas de Dados e Seus Algoritmos. Editora LTC (1994).
• D. E. Knuth, The Art of Computer Programming, Vol I: Fundamental Algorithms. Addison-Wesley (1978).
• N. Wirth, Algorithms + Data Structures = Programs. Prentice-Hall (1976).
• A. M. Tenembaum. Estruturas de Dados Usando C. Makron Books, 1995.
• N. Ziviani. Projeto de Algoritmos. Thomson, 2004.