Algoritmos e Estruturas de Dados I

Grupo de algoritmos: aqui

Pegue aqui o primeiro trabalho.

Na universidade de Yale (e em muitos outros lugares) existem reports que podem servir de inspiração para os seus relatórios. Eu acho estes aqui, aqui e aqui legais. Alguns destes relatórios tem uma página de apresentação que não é necessária para nossa disciplina.

E aqui tem uma checklist pra você saber se está indo por um bom caminho.

Uma micro-classe para desenvolver pilhas está aqui.

Uma micro-classe para desenvolver listas encadeadas está aqui.

Uma micro-classe para desenvolver árvores genéricas está aqui.

Objetivos

O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:

Ementa

Construção de soluções envolvendo diferentes algoritmos e implementações para estrutura de dados lineares e hierárquicas: filas, pilhas, listas, conjuntos, árvores e dicionários. Exame da adequação destes algoritmos na solução de diversas classes de problemas. Construção de algoritmos e implementações (usando abordagem orientada a objetos) para problemas de ordenação e pesquisa. Apresentação, discussão, análise e raciocínio sobre a complexidade dos algoritmos e implementações correspondentes.

Programa

  1. Introdução à análise de algoritmos
    1. Análise experimental
    2. Notações Assintóticas
      1. Notação O
      2. Notação Theta
      3. Notação Omega
    3. Tipos de algoritmos: logarítmico, linear, quadrático, exponencial e outros
  2. Estruturas lineares
    1. Listas, pilhas, filas
    2. Conjuntos
    3. Dicionários e tabelas hashing
  3. Pesquisa sequencial e binária
    1. Insertion sort
    2. Mergesort
    3. Quicksort
  4. Árvores
    1. Definições básicas
    2. Representação
    3. Árvores Genéricas, Binárias e de Pesquisa
    4. Caminhamentos: infixado, pré-fixado, pós-fixado
    5. Operações: pesquisa, inserção, remoção
    6. Balanceamento
    7. Heaps e heapsort
    8. Tries
    9. Aplicações

Avaliação

G1 = (P1+2*P2+2*MT)/5

Materiais

  1. Materiais da disciplina: 
    1. Notações estão aqui e uma lista de exercícios sobre notações e contagem de operações está aqui.
    2. Uma micro-classe para desenvolver listas encadeadas está aqui.
    3. Uma micro-classe para desenvolver árvores genéricas está aqui.
    4. Uma lista de exercícios sobre pesquisa e ordenação está aqui.
    5. Uma lista de exercícios sobre pilhas/listas/etc está aqui.
    6. Material para aula prática sobre árvores binárias de pesquisa:
      • A lista de exercícios está aqui.
      • Uma micro-classe para árvores binárias de pesquisa está aqui
    7. Métodos de ordenação estão aqui.
     
  2. Um pouco de tudo:
    1. Uma série de aulas do MIT (em inglês), sobre vários tópicos da disciplina e outros assuntos.
    2. Este livro é muito bom! Leia com calma e cuidado!!
    3. Um catálogo de cursos sobre algoritmos na Universidade de Pittsburgh. Fonte de outros links!
    4. Recursão, explicada em um material de Stanford. Leia tudo!!
    5. Estruturas de dados e algoritmos na McGill .Bem legal!!
    6. Design and Analysis na Universidade de Kent.
    7. Algoritmos do Skiena.
     
  3. Aulas em video na Universidade da California at Berkeley
  4. What papers should everyone read?
  5. Siga no Twitter: CompSciFact
  6. Um Wikibook inteiro sobre algoritmos.
  7. Um livro ótimo está aqui.
  8. Introdução à análise de algoritmos
    1. Material sobre somas (bem legal), na Universidade do Tennessee (Knoxville) .
    2. Somas na Univ. da California (Davis) .
    3. Um material ótimo chamado A Gentle Introduction to Algorithm Complexity Analysis. Muito bom, e você pode mandar um mail para o autor (Dionysis Zindros) agradecendo!
    4. Material sobre análise de algoritmos em Cprogramming.com.
    5. Notação O() na Wikipedia.
    6. A grande tabela sobre notação O().
     
  9. Pilhas, listas e outros
    1. Uma ótima apresentação de Princeton sobre o comportamento e implementação de pilhas, listas e outras estruturas similares.
     
  10. Ordenação e pesquisa de dados
    1. Um otimo texto sobre hashing sendo usado em criptografia no Unixwiz.
    2. Animações de algoritmos de ordenação
    3. Uma animação que inclui algoritmos paralelos no RIT.
    4. Algoritmos de ordenação na Wikipedia.
    5. Algoritmos de ordenação dançantes !!
    6. Uma coleção de algoritmos, incluindo ordenação.
     
  11. Árvores
    1. Um site que possui animações de operações em árvores binárias, AVL e B-trees: aqui .
    2. Um site bem legal com os algoritmos sobre árvores está aqui.
    3. Material simples mas interessante sobre árvores está aqui.
    4. Alguns tutoriais ótimos sobre arvores binárias, árvores AVL e árvores de Andersson estão aqui.
     

Bibliografia:

Livros texto

Livros complementares