Local: Sala F2-006.
Horário: 2as e 4as, das 8h às 10h.
Início: 7 de agosto de 2019.
-
Repositório do código criado em sala de aula:
https://github.com/vigusmao/ED_2019_2
- 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: 14/10
- P2: 27/11
- PF: 04/12
- SEGUNDA CHAMADA (apenas para quem perdeu alguma prova): a definir
- 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. O problema dos armários.
Complexidade assintótica. Notação O. Número harmônico.
Implementações distintas do problema dos armários, comparando as complexidades formais e os tempos de execução (na prática).
Código (Python) feito em sala de aula no GitHub.
O problema da celebridade. Pensando nos algoritmos em termos de complexidade assintótica.
Por quê as constantes podem de fato ficar em segundo plano. Programinha que compara funções: código no GitHub.
Discussão sobre complexidade de pior caso vs complexidade de caso médio.
O problema de se buscar um elemento presente em uma lista de n elementos com sqrt(n) cópias de cada elemento 1, 2, ..., sqrt(n). Pior caso e caso médio da busca sequencial.
Listas: alocação sequencial (arrays) vs alocação encadeada (linked lists). Principais operações, comparação de performance. Deleção física vs deleção lógica de arrays.
Implementação de listas encadeadas. Entendendo os detalhes.
Código (C) feito em sala de aula no GitHub.
Não houve aula em função da Semana da Computação.
Não houve aula em função da Semana da Computação.
Filas e pilhas. Aplicações. Implementação com arrays (de forma circular) e listas encadeadas.
Árvores. Aplicações. Representação, classificação (binária, ternária, n-ária, estritamente n-ária, completa, cheia).
Buscas (traversals) em árvores. Busca em pré-ordem, pós-ordem, ordem simétrica. Aplicações.
Árvore binária de busca ótima. Primeiras noções de Programação Dinâmica.
(Aula dada pelo Prof. Claudson Bornstein)
Árvores binárias de busca auto-balanceáveis. Árvore AVL.
(Aula dada pelo Prof. Claudson Bornstein)
Árvores red-black (rubronegras).
Revisão para a P1. O problema da representação parentisada de árvores binárias.
Código (C) feito em sala de aula (Java) no GitHub.
Resolução da lista de exercícios.
Fim da resolução da lista de exercícios.
Programação Dinâmica top-down com recursão e memoização.
P1.
Correção da P1.
Hashing. Encadeamento externo. Fator de carga.
Implementação de tabelas hash com encadeamento externo.
Término da implementação. Capacidade inicial. Rehashing.
Outras técnicas de resolução de colisões.
Tries. Radix trees. Árvores PATRICIA (ideia geral).
UNION/FIND em conjuntos disjuntos (disjoint sets). Union by rank. Path compression.
Heaps binomiais e filas de prioridade (priority queues).
Árvores B (ideia geral).
Algoritmos de ordenação. Complexidade, estabilidade, uso de memória adicional.
Selection Sort, Insertion Sort, Bubble Sort, Heap Sort, Merge Sort, Quick Sort, Count Sort, Bucket Sort.
P2.
Horário: 2as e 4as, das 8h às 10h.
Início: 7 de agosto de 2019.
https://github.com/vigusmao/ED_2019_2
- 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: 14/10
- P2: 27/11
- PF: 04/12
- SEGUNDA CHAMADA (apenas para quem perdeu alguma prova): a definir
Bibliografia sugerida
| Estruturas de Dados e seus Algoritmos | Introduction to Algorithms | ||
| (J. L. Szwarcfiter, L. Markenzon) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
07/08
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. O problema dos armários.
12/08
Complexidade assintótica. Notação O. Número harmônico.
Implementações distintas do problema dos armários, comparando as complexidades formais e os tempos de execução (na prática).
Código (Python) feito em sala de aula no GitHub.
14/08
O problema da celebridade. Pensando nos algoritmos em termos de complexidade assintótica.
Por quê as constantes podem de fato ficar em segundo plano. Programinha que compara funções: código no GitHub.
19/08
Discussão sobre complexidade de pior caso vs complexidade de caso médio.
O problema de se buscar um elemento presente em uma lista de n elementos com sqrt(n) cópias de cada elemento 1, 2, ..., sqrt(n). Pior caso e caso médio da busca sequencial.
Listas: alocação sequencial (arrays) vs alocação encadeada (linked lists). Principais operações, comparação de performance. Deleção física vs deleção lógica de arrays.
21/08
Implementação de listas encadeadas. Entendendo os detalhes.
Código (C) feito em sala de aula no GitHub.
26/08
Não houve aula em função da Semana da Computação.
28/08
Não houve aula em função da Semana da Computação.
02/09
Filas e pilhas. Aplicações. Implementação com arrays (de forma circular) e listas encadeadas.
04/09
Árvores. Aplicações. Representação, classificação (binária, ternária, n-ária, estritamente n-ária, completa, cheia).
09/09
Buscas (traversals) em árvores. Busca em pré-ordem, pós-ordem, ordem simétrica. Aplicações.
16/09
Árvore binária de busca ótima. Primeiras noções de Programação Dinâmica.
(Aula dada pelo Prof. Claudson Bornstein)
18/09
Árvores binárias de busca auto-balanceáveis. Árvore AVL.
(Aula dada pelo Prof. Claudson Bornstein)
23/09
Árvores red-black (rubronegras).
25/09
Revisão para a P1. O problema da representação parentisada de árvores binárias.
Código (C) feito em sala de aula (Java) no GitHub.
07/10
Resolução da lista de exercícios.
09/10
Fim da resolução da lista de exercícios.
Programação Dinâmica top-down com recursão e memoização.
14/10
P1.
16/10
Correção da P1.
28/10
Hashing. Encadeamento externo. Fator de carga.
30/10
Implementação de tabelas hash com encadeamento externo.
04/11
Término da implementação. Capacidade inicial. Rehashing.
Outras técnicas de resolução de colisões.
06/11
Tries. Radix trees. Árvores PATRICIA (ideia geral).
13/11
UNION/FIND em conjuntos disjuntos (disjoint sets). Union by rank. Path compression.
18/11
Heaps binomiais e filas de prioridade (priority queues).
Árvores B (ideia geral).
25/11
Algoritmos de ordenação. Complexidade, estabilidade, uso de memória adicional.
Selection Sort, Insertion Sort, Bubble Sort, Heap Sort, Merge Sort, Quick Sort, Count Sort, Bucket Sort.
27/11
P2.
