Estruturas de Dados

Horário: quartas e sextas de 7:00 às 9:00

Sala de aula virtual da disciplina: usaremos o Google Classroom para as discussões e avisos. A sala de aula no Google Classroom será usada também para divulgar avisos gerais e para dúvidas.

Monitoria

Monitores: Lucas

Horários e local de atendimento: consulte a página da monitoria.

Ementa

Árvores binárias, binárias de busca e AVL;
Grafos;
Arquivos;
Ordenação externa de arquivos (geração de partições classificadas e intercalação de partições);
Árvores B e B+ (em memória principal e secundária);
Tabelas hash (ou de dispersão) (em memória principal e secundária);
Listas de prioridade (ou heaps) (em memória principal e secundária);

Avaliação

A avaliação da disciplina é composta de duas provas (P1 e P2) e de um conjunto de trabalhos de implementação (T). A média será calculada da seguinte forma:

P1 = Prova sem consulta

P2 = Prova sem consulta

T = Média das notas dos trabalhos de implementação – todos com correção via RunCodes

\[Média = \frac{(P1 \times 2) + (P2 \times 2) + T }{5}\]

APROVADO:
\(Presença \geq 75\% ~ E ~ Média \geq 6\)

VERIFICAÇÃO SUPLEMENTAR:
\(Presença \geq 75\% ~ E ~ 4 \leq Média < 6\)

Será aprovado na VS o aluno que tirar nota maior ou igual a 6.

REPROVADO: caso contrário

Trabalhos de Implementação

Haverá um conjunto de implementações a serem entregues via GitHub Classroom. As entregas possuem data marcada e entregas atrasadas não serão aceitas. Esse item compõe a média final da disciplina, e a nota desse item será calculada pela média aritmética dos trabalhos passados ao longo do semestre. Exercícios marcados como TREINO no GitHub Classroom não contam para compor a média. Apenas exercícios marcados como AVALIAÇÃO no GitHub Classroom contam para compor a média desse item.

Listas de Exercícios

As listas de exercícios abaixo são sugeridas para auxiliar no estudo e fixação da matéria.

Video-aulas no Youtube

As aulas da disciplina estão disponíveis no Youtube. Acesse a playlist no meu canal.

Presença

De acordo com o Regulamento dos Cursos de Graduação, a presença mínima necessária para aprovação é de 75% das aulas (Art. 96) e não há abono de faltas sem documentação (Art. 103).

Bibliografia

Ferraz, I. N. Programação com Arquivos. Editora Manole Ltda. Barueri, 2003.

Szwarcfiter, J., Markenzon, L. Estruturas de Dados e Seus Algoritmos. Editora LTC, 3a. edição, 2010.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Introduction to algorithms, McGraw-Hill, 2009.

Celes, W., Cerqueira, R., Rangel, J.L. Introdução a Estruturas de Dados, Campus, 1a Edição, 2004.

Kernighan, B.W.,Ritchie, D.M. C: a linguagem de programação (Padrão ANSI), Campus, Segunda Edição, 1990.

Bibliografia Complementar

Tenenbaum, A.M., Langsam, Y., Augenstein, M.J. Estruturas de Dados Usando C, Pearson, Primeira Edição, 1995.

Ramakrishnan, R. Database Management Systems, McGraw Hill, Third Edition, 2003.

Ferramentas

IDE

Para programação em C, recomendo o CLion. É possível solicitar uma licença grátis para estudante no site da Jetbrains.

Compilador C

O CLion exige um compilador externo. Recomendo o GCC.

Para Windows, o há uma implementação do GCC chamada MinGW
Para Linux e Mac, o GCC pode ser instalado usando o gerenciador de pacotes do seu sistema operacional (normalmente o apt-get para Linux e homebrew para Mac).

Visualização de conteúdo de memória

Se você gosta de ver o que está ocorrendo na memória durante a execução do programa, recomendo o Python Tutor. Ele tem visualizadores para Python, C, C++, JavaScript e Ruby. Use o C Tutor para te ajudar a entender o que está ocorrendo na memória durante a execução do seu programa!

Memory Leak

Para ajudar na identificação de memory leak, vocês podem usar as seguintes ferramentas:

Dr. Memory (funciona em todas as plataformas)
Valgrind (específico para Linux)

AVL

Use esse site para simular inserções e remoções em árvores AVL de forma visual.

Cronograma

Data	Atividade
30/08/2023	Apresentação da disciplina
01/09/2023	Revisão de C
06/09/2023	Aula no Laboratório
08/09/2023	SEM AULA - FERIADO
13/09/2023	Árvores e Árvores Binárias Implementação de Árvore Binária Material de Apoio: Revisão de Pilhas e Filas em C
15/09/2023	Árvores Binárias de Busca Implementação de Busca e Inserção em Árvore Binária de Busca
20/09/2023	Aula no Laboratório
22/09/2023	Árvores AVL
27/09/2023	Grafos
29/09/2023	Aula no Laboratório
04/10/2023	Arquivos Tutorial de Acesso a Arquivos em C
06/10/2023	Aula no Laboratório
11/10/2023	Ordenação de Arquivos Insertion Sort em Memória e em Disco para Ordenar Arquivos Ordenação Externa de Arquivos: Geração de Partições Classificadas Implementação de Classificação Interna
13/10/2023	SEM AULA - FERIADO
18/10/2023	SEM AULA - AGENDA ACADÊMICA
20/10/2023	SEM AULA - AGENDA ACADÊMICA
25/10/2023	PROVA 1
27/10/2023	Ordenação Externa de Arquivos: Intercalação de Partições Classificadas Implementação de Intercalação
01/11/2023	Árvore B Implementação de Busca e Inserção em Árvore B em memória
03/11/2023	SEM AULA - FERIADO
08/11/2023	Árvore B (continuação)
10/11/2023	AULA CANCELADA por problemas de saúde: fazer o exercício postado no GitHub Classroom
15/11/2023	SEM AULA - FERIADO
17/11/2023	AULA CANCELADA por problemas de saúde: assistir a vídeo aula e acompanhar os slides sobre Árvore B+
22/11/2023	Tabelas Hashi. Tratamento de colisão por encadeamento exterior. Implementação Básica de Tabela Hash em memória (Essa implementação não trata colisões) Implementação de Tabela Hash em memória com tratamento de colisões por Encadeamento Exterior
24/11/2023	Aula no Laboratório + Vista de Prova
29/11/2023	Heap Implementação em memória Implementação em disco
01/12/2023	Aula de dúvidas
06/12/2023	PROVA 2
08/12/2023	SEGUNDA CHAMADA (sala 213)
13/12/2023	VISTA DE P2 e SEGUNDA CHAMADA (sala 521)
15/12/2023	VS (sala 213)
20/12/2023	VISTA DE VS (sala 521)

Vanessa Braganholo

Menu: