Estruturas de Dados / Organização de Dados I  —  2016/2

Página principal

Informações

Bibliografia sugerida

Estruturas de Dados e seus Algoritmos     Introduction to Algorithms    
(J. L. Szwarcfiter, L. Markenzon)     (Cormen, Leiserson, Rivest & Stein)    
         


Conteúdo das aulas

12/09


Primeira conversa sobre o curso: derrotando o código alheio.
Por que entender de estruturas de dados e complexidade de algoritmos?
Probleminha pra quebrar o gelo: dados dois arrays (listas) de inteiros, encontrar sua interseção.  
 

14/09


Lista linear: a estrutura mais simples. Alocação sequencial (arrays) e encadeada (listas encadeadas).
Operações mais comuns (nas duas implementações): ler o k-ésimo elemento da lista; inserir no começo da lista; inserir no fim da lista (append); concatenar listas; remover um elemento.
Políticas de crescimento de listas em alocação sequencial (arrays): crescimento em P.A. (tempo total quadrático) e em P.G. (tempo total linear).  
 

19/09


Busca de elemento em array ordenado: (1) parando entes de chegar ao fim; (2) busca binária!

Implementação do problema da interseção.
Código (em Python) feito em sala de aula no GitHub.  
 

21/09


Comparando a ementa do curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.

Análise de algoritmos: discussão sobre o número de "passos" de um programa, i.e., a quantidade de operações básicas que são executadas, ou, equivalentemente, de blocos com número constante de operações de tempo constante que são executados. Complexidade assintótica. A notação O.  
 

26/09


Implementação de listas encadeadas "from scratch" em C. Código feito em sala de aula no GitHub.  
 

28/09


Continuação de listas encadeadas. Remoção, concatenação, etc.  
 

03/10


Filas e pilhas. Implementação usando arrays e usando listas encadeadas.  
 

05/10


Árvores. Árvores binárias.
Busca em árvores. Percurso em pré-ordem, pós-ordem, ordem simétrica, largura. Exemplos de aplicação.  
 

10/10


Discussão sobre programas recursivos versus não-recursivos: nenhum problema em usar recursão, desde que se evite resolver o mesmo subproblema inúmeras vezes. Exemplo: Fibonacci.
Código feito em sala de aula no GitHub.

Árvore binária de busca.  
 

24/10


Frequências de acesso distintas. Árvore binária de busca ótima.  
 

26/10


Implementação recursiva (com memoização) do algoritmo da árvore binária de busca ótima.
Código feito em sala de aula no GitHub.

Árvores auto-balanceáveis. Árvore AVL.  
 

31/10


Revisão para a P1. Correção da primeira lista.  
 

07/11


P1.  
 

09/11


Correção da P1 em sala de aula.  
 

16/11


Hashing. Tratamento de colisões via encadeamento externo.  
 

21/11


Complexidade esperada para operações de dicionário.
Outras formas de tratar colisões.
Cuckoo hashing.  
 

23/11


Heaps.  
 

28/11


Algoritmos de ordenação. Tempo. Espaço. Estabilidade.
Selection Sort. Insertion Sort. Bubble Sort.
Merge Sort. Heap Sort. Quick Sort.  
 

30/11


A complexidade de caso médio do Quick Sort.
Ordenando em tempo O(log n). Count Sort.  
 

05/12


P2.  
 

Voltar ao topo