Algoritmos e Estruturas de Dados 1

Turmas A e B - 2s2022

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 213 ter 14h-18h.
  
  
• Turma B
  Local e horário das aulas: AT5 99 qui 14h-18h.
  

Tópicos das Aulas

1. Apresentação, análise de algoritmos intuitiva, laços aninhados e logaritmos
   Vídeos da aula 01: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópicos Leiaute, Documentação e Logaritmos do Projeto de Algoritmos (em C), Seção 1.1 do Estruturas de Dados e Técnicas de Programação.
2. Recursão, fatorial e torres de Hanoi
   Vídeos da aula 02: Playlist.
   Notas de aula: PDF.
   Bibliografia: Seção 5.1 do Estruturas de Dados e Técnicas de Programação.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 01, Aula 03.
   
3. Recursão, exponencial, Fibonacci, análise de desempenho
   Vídeos da aula 03: Playlist.
   Notas de aula: PDF.
   Bibliografia: Seção 5.1 do Estruturas de Dados e Técnicas de Programação.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 02.
   
4. Recursão, máximo divisor comum, algoritmo de Euclides
   Vídeos da aula 04: Playlist.
   Notas de aula: PDF.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 03, Aula 04.
   
5. Recursão, máximo, crescimento de funções, binomial (bônus)
   Vídeos da aula 05: Playlist.
   Vídeos da aula bônus: Playlist.
   Notas de aula: PDF, PDF Bônus.
   Bibliografia: Tópico Recursão e algoritmos recursivos do Projeto de Algoritmos (em C).
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 02.
   
6. Busca sequencial e binária em vetores
   Vídeos da aula 06: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópico Busca em vetor ordenado do Projeto de Algoritmos (em C).
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 17.
   
7. Endereços, apontadores e estruturas
   Vídeos da aula 07: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópicos Endereços e ponteiros, Registros e structs e Entrada e saída do Projeto de Algoritmos (em C).
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 05.
   
8. Alocação dinâmica de memória
   Vídeos da aula 08: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópico Alocação dinâmica de memória do Projeto de Algoritmos (em C), Capítulo 2 do Estruturas de Dados e Técnicas de Programação.
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 06.
   
9. Lista em vetor
   Vídeos da aula 09: Playlist.
   Notas de aula: PDF.
   Bibliografia: Tópico Vetores do Projeto de Algoritmos (em C).
   Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 07.
   
10. Lista ligada
    Vídeos da aula 10: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Listas ligadas do Projeto de Algoritmos (em C), Seção 3.1 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 08.
    
11. Listas ligadas com nó cabeça, circulares e duplamente ligadas
    Vídeos da aula 11: Playlist.
    Notas de aula: PDF, PDF Bônus.
    Bibliografia: Tópico Listas ligadas do Projeto de Algoritmos (em C), Seções 3.2 e 3.3 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 09.
    
12. Pilha implementada em vetor, aplicação com parênteses e colchetes, pilha de execução, relação de pilha com recursão
    Vídeos da aula 12: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Pilhas do Projeto de Algoritmos (em C), Seção 4.2 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides da aula do prof. José Coelho de Pina Junior Aula 10.
    
13. Pilhas, inversão de sequências, notação infixa para pósfixa, conversão de recursão para iteração
    Vídeos da aula 13: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Pilhas do Projeto de Algoritmos (em C), Seções 4.3 e 5.2 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides da aula do prof. José Coelho de Pina Junior Aula 11.
    
14. Pilhas em listas ligadas, bibliotecas e interfaces
    Vídeos da aula 14: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópicos Pilhas e Bibliotecas de funções do Projeto de Algoritmos (em C), Seção 4.2 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides da aula do prof. José Coelho de Pina Junior Aula 12, Aula 13.
    
15. Revisão de recursão, inversão de uma lista ligada (bônus)
    Vídeos da aula 15 bônus: Playlist.
    
16. Fila implementada em vetor, cálculo de distâncias, interfaces
    Vídeos da aula 16: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Filas do Projeto de Algoritmos (em C), Seção 4.4 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides da aula do prof. José Coelho de Pina Junior Aula 14.
    
17. Filas em vetor circular e em listas ligadas, interfaces, listas de adjacência
    Vídeos da aula 17: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Filas do Projeto de Algoritmos (em C), Seção 4.4 do Estruturas de Dados e Técnicas de Programação.
    Material complementar: Slides da aula do prof. José Coelho de Pina Junior Aula 15.
    
18. Árvores binárias
    Vídeos da aula 18: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Árvores binárias do Projeto de Algoritmos (em C).
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 25.
    
19. Filas de prioridade: implementações básica e com heap
    Vídeos da aula 19: 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.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 21 e vídeo aulas do prof. Tim Roughgarden 12 3.
    
20. Ordenação por inserção (insertionSort) e por transposição (bubbleSort)
    Vídeos da aula 20: 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.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 18.
    
21. Embaralhamento de Knuth, ordenação por seleção (selectionSort)
    Vídeos da aula 21: Playlist.
    Notas de aula: PDF.
    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.
    
22. Ordenação por seleção eficiente (heapSort), construção de heap em tempo linear (heapify)
    Vídeos da aula 22: Playlist.
    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.
    
23. Tabelas de símbolos, implementação em vetores ordenados, árvores binárias de busca
    Vídeos da aula 23: Playlist.
    Notas de aula: PDF.
    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 25 e vídeo aulas do prof. Tim Roughgarden 13 1, 13 2, 13 3.
    
24. Árvores binárias de busca (operações avançadas), tabelas de símbolos
    Vídeos da aula 24: Playlist.
    Notas de aula: PDF.
    Bibliografia: Seções 11.2 e 11.3 do Algorithms Illuminated, Part 2, Tópico Á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.
    
25. Algoritmos de enumeração
    Vídeos da aula 25: Playlist.
    Notas de aula: PDF.
    Bibliografia: Tópico Algoritmos de enumeração do Projeto de Algoritmos (em C).
    
26. Programação com retrocesso (backtracking)
    Vídeos da aula 26: Playlist.
    Slides da aula: PDF.
    Bibliografia: Seção 9.1 do Algorithms.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 24.
    
27. Problemas da seleção e da contagem de inversões
    Vídeos da aula 27: Playlist.
    Notas de aula: PDF.
    Material complementar: Slides das aulas do prof. José Coelho de Pina Junior Aula 20.
    

Listas de Exercícios

1. Recursão: PDF.
2. Vetores e busca: PDF.
3. Listas ligadas: PDF.
4. Pilhas: PDF.
5. Filas: PDF.
6. Árvores binárias, heaps: PDF.
7. Ordenação: PDF.
8. Árvores binárias de busca: PDF.

Bibliografia e Materiais Recomendados

• Feofiloff, P.. 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
• R. Sedgewick. Algorithms in C, Parts 1-4: fundamentals, data structures, sorting, searching. 3rd. ed., Addison-Wesley, 1998.
• Lucchesi, C.L., Kowaltowski, T.. Estruturas de Dados e Técnicas de Programação. Versão 1.12, 2004. PDF
• Aaron M. Tenenbaum, Yedidyah Langsam, Moshe J. Augenstein. Estruturas de dados usando C. São Paulo: Pearson Makron Books, 2009.
• Ferrari, R., Ribeiro, M. X., Dias, R. L., Falvo, M. Estruturas de Dados com Jogos. Rio de Janeiro – Elsevier, 2014. LINK
• Nivio Ziviani. Projetos de algoritmos: com implementações em Pascal e C. 3a ed. rev. e ampl., São Paulo: Cengage Learning, 2012.
• E.S. Roberts. Programming Abstractions in C: a Second Course in Computer Science. Addison-Wesley, 1997.
• R.R. Ciferri. Programação de Computadores. Edufscar, 2009.