MC3305 - Algoritmos e Estruturas de Dados II

TPI: 2 - 2 - 4

Agenda

Aula   Data   Conteúdo previsto Lista (prazo de entrega) 1 26/05 Apresentação Custo de um algoritmo, Funções de complexidad e Recursão [atividade] 2 28/05 Tabelas de dispersão [Laboratório] 3 02/06 Limite assintótico para a ordenação, ordenação em tempo linear (counting sort, radix sort, bucket sort) [atividade] Desafio 01: Data de entrega 09/06 (23h50) - 04/06 Recesso (Corpus Christi) 4 09/06 Ordenação parcial (Seleção, Inserção, Heapsort, Quicksort) [atividade] Lista 01: Data de entrega 18/06 (23h50) 5 11/06 Ordenação parcial (Heapsort). Comparação empírica entre algoritmos de ordenação parcial [Laboratório] 6 16/06 Árvores: representação, percurso, conversão de uma floresta, árvores com costura [atividade] Desafio 02: Data de entrega 25/06 (23h50) 7 18/06 Árvores, árvores binárias de busca, busca e inserção de elementos [Laboratório] 8 23/06 Árvores binárias de busca [atividade] Lista 02: Data de entrega 12/07 (23h50) 9 25/06 Árvores binárias de busca e Árvores de Huffman [Laboratório] 10 30/06 Árvores AVL [ atividade | avl paper ] 11 02/06 Árvores AVL [Laboratório] 12 07/07 Prova 01 - 09/07 Recesso (Revolução Constitucionalista) 13 14/07 Árvores Rubro-Negras (Red-Black) [ atividade | redblack paper ] Lista 03: Data de entrega 23/07 (23h50) 14 16/07 Árvores Rubro-Negras (Red-Black) [Laboratório] 15 21/07 Árvores TRIE [ trie paper ] 16 23/07 Árvores TRIE [Laboratório] Lista 04: Data de entrega 30/07 (23h50) 17 28/07 Árvores PATRICIA e Árvores B [ patricia paper ] 18 30/07 Árvores B e parâmetros de compilação [Laboratório] Desafio 03: Data de entrega 13/08 (23h50) 19 04/08 Conjuntos disjuntos (Union-Find) 20 06/08 Conjuntos disjuntos (Union-Find) [Laboratório] Lista 05: Data de entrega 20/08 (23h50) 21 11/08 Ordenação externa 22 13/08 Aula de revisão [Laboratório] 23 18/08 Prova 02 24 25/08 Prova Substitutiva (Para as 2 turmas: 14hrs, Sala 301-3, único horário) 25 15/09 Prova REC (Para as 2 turmas: 14hrs, Sala 301-3, único horário) (Precisa enviar um email para confirmar presença)

>>>> Notas Finais
[A vista da prova 2 para ambas as turmas será dia 25/08 às 13h30 na sala 301-3]

Plano de ensino.

Programa resumido
Ponteiros e estruturas, recursão, limite assintótico para a ordenação em memória primária, algoritmos de ordenação parcial, algoritmos de ordenação em tempo linear, árvores binárias, varredura em árvores, árvores Adelson-Velskii e Landis (AVL), rubro-negras (Red-Black), TRIE, PATRICIA, e B/B*. Tabelas de dispersão (hashing), Conjuntos disjuntos (Union-Find) . Ordenação externa (mergesort).

Livro-texto

• SZWARCFITER, J. L.; MARKEZON, L. Estruturas de Dados e seus Algoritmos, 3a edição, LTC, 2010.

• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C. Introduction to Algorithms, 3a edição, MIT Press, 2009.
• ZIVIANI, N. Projeto de Algoritmos: com implementações em Pascal e C, 2a edição, Cengage Learning, 2009.
• FOLK, M.; ZOELLICK B. File Structures, 2a edição, Addison-Wesley, 1992.
• FOLK, M.; ZOELLICK, B.; RICCARDI, G. File Structures, An Object-Oriented Approach Using C++, 3a edição, Addison-Wesley, 1998.
• SEDGEWICK, R. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3a edição. Addison-Wesley, 1997.

• HackerRankd
• Cloul9
• GCC (GNU Compiler Collection)
• Cygwin (para windows)
• cdecl
  
• Data struture visualizations
• Sorting:
  • Sorting Algorithm Animations
  • Sortvis
  • Sorting
  • 15 Sorting Algorithms in 6 Minutes
• Ascii table
• Programming in movies vs. programming in real life