Local: Sala no Google Meet: meet.google.com/znx-iepz-gca
Horário: 2as e 4as, das 8h às 10h.
Início: 17 de novembro de 2021.
-
Repositório do código criado em sala de aula.
- Ementa aproximada:
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Hashing;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Programação dinâmica e memoização;
- Conjuntos disjuntos;
- Heaps;
- Algoritmos de ordenação.
- Avaliação:
M = (P1 + P2) / 2 ≥ 6.0 --> aprovação direta;
do contrário, MF = (M + PF) / 2 ≥ 5.0 --> aprovação;
MF < 5.0 --> reprovação.
- Provas:
- P1: 17/01/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] P1" até as 10:30)
- P2: 07/03/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] P2" até as 10:30)
- PF: 09/03/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] PF" até as 10:30)
- Primeira lista de exercícios aqui.
- Segunda lista de exercícios aqui.
Primeira conversa sobre o curso: derrotando o código alheio.
(Comparem a ementa deste curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.)
Começando a pensar em complexidade de algoritmos, e a compará-las.
Programinha em Python para visualização de funções que tipicamente representam complexidades assintóticas.
Gravação da aula.
Complexidade de tempo e de espaço. Análise de pior caso e caso médio.
Exemplo: o problema do par com a menor diferença absoluta.
Implementação em Python de um algoritmo O(n^2).
Gravação da aula.
Comportamento assintótico, notação O (Big-Oh): entendendo como cresce o tempo (ou espaço) utilizado por um algoritmo em função do tamanho da entrada.
Um segundo algoritmo para o problema do par com a menor diferença absoluta.
Gravação da aula.
O problema da celebridade (código em Python). Algoritmo quadrático vs algoritmo linear.
Por que você não deve nunca mais simplesmente escrever algo "que funcione", sem se preocupar se performance pode ser um problema.
Gravação da aula.
Formalização dos conceitos de notação Grande-O, Ômega e Theta. Gravação da aula.
Listas lineares. Implementação sequencial (arrays) versus implementação encadeada (listas encadeadas).
Listas simplesmente encadeadas e listas duplamente encadeadas. Vantagens e desvantagens em comparação com arrays.
Remoção de elementos de um array usando thombstones (lápides). Vantagens e desvantagens.
Gravação da aula.
Código (em C) feito em aula. Jamboard com rascunhos e notas de aula.
Seguindo com a comparação entre arrays e listas encadeadas.
Busca binária (em arrays ordenados). Vale a pena ordenar um array para depois rodar uma busca binária? E se você for rodar uma quantidade muito grande de buscas no mesmo array?
Gravação da aula.
Rascunhos da aula.
Implementação de listas encadeadas em C e em Java.
Gravação da aula.
Filas e pilhas. Uso. Maneiras diferentes (eficientes) de implementá-las: (1) usando listas encadeadas, (2) usando arrays com indicadores de começo e fim (fila) ou de topo (pilha).
Políticas de crescimento de arrays em progressão aritmética e em progressão geométrica.
Gravação da aula.
Finalização da implementação (em Java) de filas e pilhas usando listas encadeadas e usando arrays. Testes comparativos de performance. Unit tests.
Exemplo de uso de pilha: verificar parentização>/a> de expressões aritméticas.
Gravação da aula.
Árvores. Árvores n-árias. Árvores completas. Implementação usando array (para árvores estritamente n-árias) e usando alocação randômica e ponteiros.
Percursos em árvores: pré-ordem, em-ordem (intra-ordem) e pós-ordem. Aplicações desses percursos.
Árvores binárias de busca.
Gravação da aula.
Anotações de aula.
Árvore binária de busca de altura mínima. Construção. Construção dada a sequência de visitas em um percurso em pré-ordem.
Código (Java) para árvores binárias, e para a aplicação de busca em pré-ordem para se determinar o nível de cada nói na árvore.
Gravação da aula. Anotações de aula no link da aula anterior.
Mais aplicações práticas de percursos em pré-ordem, intra-ordem e pós-ordem. Implementação (Java) da verificação de uma árvore binária quanto a ser ou não uma árvore binária de busca.
Código Python para comparação de implementações recursivas para fatorial e n-ésimo número de Fibonacci. Subproblemas repetidos. Por que a implementação recursiva natural do n-ésimo Fibonacci fica com performance extremamente ruim? (Cenas dos próximos capítulos: Programaçao Dinâmica e memoização.)
Gravação da aula.
Anotações de aula no link da aula do dia 05/01.
P1.
Correção da P1.
Gravação da aula.
Programação dinâmica. Bottom-up vs top-down (com memoização).
O problema da Árvore Binária de Busca Ótima para frequências de acesso conhecidas.
Gravação da aula.
Implementando a soluçao via Programação Dinâmica para o problema da árvore binária de busca ótima (com frequências de acesso dadas).
Gravação da aula.
Mais sobre Programação Dinâmica: bottom-up (PD clássica) versus top-down (PD via memoização): implementação de solução para o problema da mochila.
Vantagem de se fazer top-down: (1) a escrita recursiva é muito natural; (2) acaba-se evitando em muitos casos que toda a tabela seja preenchida, mas apenas as células realmente necessárias.
Gravação da aula.
Finalizando a implementação do problema da mochila via PD. Comparando bottom-up e top-down mais uma vez, e reforçando a "receita de bolo" para memoização.
Gravação da aula.
Hashing. Técnicas para tratamento de colisões.
Gravação da aula.
Implementação de uma tabela hash em C. Comparativo entre uso de tabela hash, lista e árvore binária de busca auto-balanceada.
Gravação da aula.
Heaps. Heap binária de máximo e de mínimo. Implementação de heap binária sobre um array. Construção da heap em tempo O(n).
Filas de prioridades.
Ordenando com heaps: o algoritmo HeapSort.
Anotações da aula.
Gravação da aula.
Algoritmos de ordenação. Complexidade. Estabilidade. Uso adicional de memória.
BucketSort, InserionSort, QuickSort, MergeSort, HeapSort, CountSort, BucketSort.
Anotações da aula.
Gravação da aula.
Tries. Árvores de prefixo. Aplicações.
Anotações da aula.
Gravação da aula.
Union/Find. Estruturas de dados para conjuntos disjuntos (disjoint sets).
Anotações da aula (mesmo documento da aula de Tries).
Gravação da aula.
Horário: 2as e 4as, das 8h às 10h.
Início: 17 de novembro de 2021.
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Hashing;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Programação dinâmica e memoização;
- Conjuntos disjuntos;
- Heaps;
- Algoritmos de ordenação.
M = (P1 + P2) / 2 ≥ 6.0 --> aprovação direta;
do contrário, MF = (M + PF) / 2 ≥ 5.0 --> aprovação;
MF < 5.0 --> reprovação.
- P1: 17/01/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] P1" até as 10:30)
- P2: 07/03/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] P2" até as 10:30)
- PF: 09/03/22 (PDF da prova, entrega por e-mail (vigusmao@dcc.ufrj.br), com assunto "[ED-2021-2] PF" até as 10:30)
Bibliografia sugerida
| Estruturas de Dados e seus Algoritmos | Introduction to Algorithms | ||
| (J. L. Szwarcfiter, L. Markenzon) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
17/11
Primeira conversa sobre o curso: derrotando o código alheio.
(Comparem a ementa deste curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.)
Começando a pensar em complexidade de algoritmos, e a compará-las.
Programinha em Python para visualização de funções que tipicamente representam complexidades assintóticas.
Gravação da aula.
22/11
Complexidade de tempo e de espaço. Análise de pior caso e caso médio.
Exemplo: o problema do par com a menor diferença absoluta.
Implementação em Python de um algoritmo O(n^2).
Gravação da aula.
24/11
Comportamento assintótico, notação O (Big-Oh): entendendo como cresce o tempo (ou espaço) utilizado por um algoritmo em função do tamanho da entrada.
Um segundo algoritmo para o problema do par com a menor diferença absoluta.
Gravação da aula.
01/12
O problema da celebridade (código em Python). Algoritmo quadrático vs algoritmo linear.
Por que você não deve nunca mais simplesmente escrever algo "que funcione", sem se preocupar se performance pode ser um problema.
Gravação da aula.
06/12
Formalização dos conceitos de notação Grande-O, Ômega e Theta. Gravação da aula.
08/12
Listas lineares. Implementação sequencial (arrays) versus implementação encadeada (listas encadeadas).
Listas simplesmente encadeadas e listas duplamente encadeadas. Vantagens e desvantagens em comparação com arrays.
Remoção de elementos de um array usando thombstones (lápides). Vantagens e desvantagens.
Gravação da aula.
Código (em C) feito em aula. Jamboard com rascunhos e notas de aula.
13/12
Seguindo com a comparação entre arrays e listas encadeadas.
Busca binária (em arrays ordenados). Vale a pena ordenar um array para depois rodar uma busca binária? E se você for rodar uma quantidade muito grande de buscas no mesmo array?
Gravação da aula.
Rascunhos da aula.
15/12
Implementação de listas encadeadas em C e em Java.
Gravação da aula.
20/12
Filas e pilhas. Uso. Maneiras diferentes (eficientes) de implementá-las: (1) usando listas encadeadas, (2) usando arrays com indicadores de começo e fim (fila) ou de topo (pilha).
Políticas de crescimento de arrays em progressão aritmética e em progressão geométrica.
Gravação da aula.
22/12
Finalização da implementação (em Java) de filas e pilhas usando listas encadeadas e usando arrays. Testes comparativos de performance. Unit tests.
Exemplo de uso de pilha: verificar parentização>/a> de expressões aritméticas.
Gravação da aula.
05/01
Árvores. Árvores n-árias. Árvores completas. Implementação usando array (para árvores estritamente n-árias) e usando alocação randômica e ponteiros.
Percursos em árvores: pré-ordem, em-ordem (intra-ordem) e pós-ordem. Aplicações desses percursos.
Árvores binárias de busca.
Gravação da aula.
Anotações de aula.
10/01
Árvore binária de busca de altura mínima. Construção. Construção dada a sequência de visitas em um percurso em pré-ordem.
Código (Java) para árvores binárias, e para a aplicação de busca em pré-ordem para se determinar o nível de cada nói na árvore.
Gravação da aula. Anotações de aula no link da aula anterior.
12/01
Mais aplicações práticas de percursos em pré-ordem, intra-ordem e pós-ordem. Implementação (Java) da verificação de uma árvore binária quanto a ser ou não uma árvore binária de busca.
Código Python para comparação de implementações recursivas para fatorial e n-ésimo número de Fibonacci. Subproblemas repetidos. Por que a implementação recursiva natural do n-ésimo Fibonacci fica com performance extremamente ruim? (Cenas dos próximos capítulos: Programaçao Dinâmica e memoização.)
Gravação da aula.
Anotações de aula no link da aula do dia 05/01.
17/01
P1.
19/01
Correção da P1.
Gravação da aula.
24/01
Programação dinâmica. Bottom-up vs top-down (com memoização).
O problema da Árvore Binária de Busca Ótima para frequências de acesso conhecidas.
Gravação da aula.
26/01
Implementando a soluçao via Programação Dinâmica para o problema da árvore binária de busca ótima (com frequências de acesso dadas).
Gravação da aula.
31/01
Mais sobre Programação Dinâmica: bottom-up (PD clássica) versus top-down (PD via memoização): implementação de solução para o problema da mochila.
Vantagem de se fazer top-down: (1) a escrita recursiva é muito natural; (2) acaba-se evitando em muitos casos que toda a tabela seja preenchida, mas apenas as células realmente necessárias.
Gravação da aula.
02/02
Finalizando a implementação do problema da mochila via PD. Comparando bottom-up e top-down mais uma vez, e reforçando a "receita de bolo" para memoização.
Gravação da aula.
07/02
Hashing. Técnicas para tratamento de colisões.
Gravação da aula.
09/02
Implementação de uma tabela hash em C. Comparativo entre uso de tabela hash, lista e árvore binária de busca auto-balanceada.
Gravação da aula.
14/02
Heaps. Heap binária de máximo e de mínimo. Implementação de heap binária sobre um array. Construção da heap em tempo O(n).
Filas de prioridades.
Ordenando com heaps: o algoritmo HeapSort.
Anotações da aula.
Gravação da aula.
16/02
Algoritmos de ordenação. Complexidade. Estabilidade. Uso adicional de memória.
BucketSort, InserionSort, QuickSort, MergeSort, HeapSort, CountSort, BucketSort.
Anotações da aula.
Gravação da aula.
21/02
Tries. Árvores de prefixo. Aplicações.
Anotações da aula.
Gravação da aula.
23/02
Union/Find. Estruturas de dados para conjuntos disjuntos (disjoint sets).
Anotações da aula (mesmo documento da aula de Tries).
Gravação da aula.
