INF1010 3WB – Estruturas de Dados Avançadas - 2018.1

Atenção:
Este site é o da turma B. Se voce for aluno do Prof. Casanova, o site da turma A é outro.
Esta páginas é constantemente atualizada durante o curso.

Professores:

Marcelo Gattass e Suellen Motta
e-mail: profs-eda@tecgraf.puc-rio.br
sala: Instituto Tecgraf, sexto andar, prédio Pe. Laércio Dias de Moura.

Horário:

2^as de 15-17h, 234L
4^as de 15-17h, 234L

Objetivo:

Estrutura de Dados são os blocos de construção básicos para a organização das informações em algoritmos e programas. O curso visa apresentar e permitir compreender as principais estruturas de dados avançadas, como implementar, usar e aplicar elas em códigos genéricos.

Programa:

• Módulo 1: Árvores Auto Balanceadas

1. Árvores Binárias de Busca.
2. Introdução a Complexidade de Algoritmos.
3. Introdução ao C++ - aula 1.
4. Árvores Binárias Balanceadas: AVL e Vermelha-Preta.
5. Árvores N-árias Balanceadas: B, B+ e 2-3.

• Módulo 2: Hash, Heap e Partição Dinâmica

1. Filas de Prioridade: Heap.
2. Aula de Templates em C++.
3. Tabelas de Dispersão: Hash Table.
4. Aula de iteradores em C++.
5. Aula de STL (Standard Template Library em C++.
6. Partição Dinâmica .

• Módulo 3: Grafos

1. Grafos.
2. Aplicação de Grafos.
3. Outras estruturas importantes.

Provas: (na sala e horário de aula)

• P1 - Módulo 1 - data: 11 de abril.
• P2 - Módulo 2 - data: 28 de maio.
• P3 - Módulo 3 - data: 04 de julho.
• P4 - Todos os Módulos - data: 09 de julho.

Listas de Exercícios:

• Complexidade.
• Árvores Binarias de Busca.
• Árvores Rubro-negras (RBTree).
• Heap.
• Hash.
• Grafo.
• Partição Dinâmica.

Trabalhos:

1. T1 - ABB: Arvore Binária de Busca - entrega: 26 de março.
2. T2 - Red Black Tree - entrega: 11 de abril.
3. T3 - Heap - entrega: 07 de maio.
4. T4 - Hash - entrega: 28 de maio.
5. T5 - Grafo I - entrega: 18 de junho.
6. T6 - Grafo II - entrega: 04 de julho.

Avaliação: Critério 4 do CB da PUC

Onde G1, G2 e G3 são obtidos como 80% da Prova e 20% do Trabalho.

G4 é a nota da P4.

Pré-requisito:

Prog I e Prog. II.

Leitura Recomendada

• Uma boa introdução da arvore binária de busca. Note apenas que o que ele chama de "full tree" é o que chamamos de "estritamente binária". A definição que utilizamos para arvore cheia é outra. É uma árvore binária completa (ou complete tree) com o último nível totalmente preenchido.
• Uma boa introdução a Complexidade

Bibliografia:

• CELES, W.; CERQUEIRA, R.F.G.; RANGEL, J.L., Introdução a Estruturas de Dados - Editora Campus.
• DROZDEK. A., Data Structures and Algorithms in C++, 4th Edition - CENGAGE Learning.
• TENENBAUM, A.M.; LANGSAM, Y.; AUGENSTEIN, M., Estruturas de Dados Usando C, Makron Books, 1995.