CIC102 - Algoritmos e Estruturas de Dados I / 2o. semestre de 2009

CIC102 – Algoritmos e Estruturas de Dados I

Carga Horária: 90 Horas de Aula ou 108 Horas Aula (72h – Teórica / 36h – Prática = 6 créditos)

Professor: David Menotti (menottid@gmail.com)

Monitor: Kayran dos Santos (kayransantos2@gmail.com)

Monitor: Pedro Ismar Silva Souto (pedro.ismar.777@gmail.com)

2º Semestre de 2009

Novidades

Resultado final - verifique sua situação (28/12/2009 – 20:00)

Disponível texto do exame especila (28/12/2009 – 20:00)

Verifique sua situação (16/12/2009 – 22:10)

Disponível notas e frequência (16/12/2009 – 22:10)

Disponível texto e gabarito do terceiro teste (16/12/2009 – 22:00)

Adiada para 10/12 as 20:00/20:30 (moodle/impresso) a entrega do TP6 (09/12/2009 – 19:20)

Adiada para 16/12 o terceiro e último teste e para 23/12 o exame especial (03/12/2009 – 18:00)

Adiada para 09/12 a entrega do TP6 (03/12/2009 – 18:00)

Disponível Trabalho Prático 6 (19/11/2009 – 18:00)

A documentação impressa do TP5 deve ser entregue na sala COM25 (LaPDI) para os monitores até as 16h desta sexta-feira (19/11/2009 – 17:55)

Notas atualizadas – faltando somente 3,2 pontos (3º. Teste (2,0), TPs 5 e 6 (1,0), Listas (0,1) e Aula de Lab. (0,1)) (18/11/2009 – 13:34)

Mais uma atualização no código do TP5 [código] (17/11/2009 – 17:00)

Atualização no código do TP5 [código] (12/11/2009 – 20:50)

Adiada a data de entrega dos TP5 e TP6 (12/11/2009 – 17:10)

2o. Teste adiado para 12/11/2009 (quinta-feira) (05/11/2009 – 21:10)

Atualização no enunciado e código do TP5 Trabalho Prático 5 [código] (05/11/2009 – 21:10)

Notas atualizadas – faltando somente TP3 e TP4 (10/11/2009 – 21:10)

Disponível Trabalho Prático 5 [código] (05/11/2009 – 20:00)

Selecionados melhores Trabalhos Práticos 2 (29/10/2009 – 21:00)

Slides das últimas aulas, atualizados (29/10/2009 – 21:00)

Disponível Trabalho Prático 4 (23/10/2009 – 19:00) – anteriomente disponível em CICGERAL

Disponível Trabalho Prático 3 (08/10/2009 – 17:45)

Disponível texto do primeiro teste (08/10/2009 – 14:15)

Disponível notas do primeiro teste (06/10/2009 – 11:25)

Slides das aulas téoricas atualizados (01/10/2009 – 21:40)

Disponível Trabalho Prático 2 (21/09/2009 – 15:20)

Disponível Trabalho Prático 1 (24/08/2009 – 19:05)

Divulgado o horário de monitoria (20/08/2009 – 15:40)

Divulgadas datas para entrega dos trabalhos práticos – planeje-se! (20/08/2009 – 00:30)

Divulgado o cronograma tentativo para a disciplina (19/08/2009 – 23:30)

Horário:

Quarta-feira das 17:10 as 18:50, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 21 e 22 - Sala 1 (ICEB I) - Teórica

Quinta-feira das 15:20 as 17:00, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 21 e 22 - Sala 9 (ICEB I) – Teórica

Terça-feira das 21:00 as 22:40, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 21 e 22 - Sala 3 (ICEB I) – Reforço Teórico

Quinta-feira das 19:00 as 20:40, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 21 e 22 - Sala 7 (ICEB I) – Reforço Teórico

Quarta-feira das 13:30 as 15:10, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 21 - Sala COM30 (ICEB I) – Prática

Quinta-feira das 13:30 as 15:10, Instituto de Ciência Exatas e Biológicas - ICEB

Turma 22 - Sala COM30 (ICEB I) – Prática

Segunda-feira das 16:00 as 19:00, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Kayran)

Terça-feira das 20:40 as 21:40, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Kayran)

Quinta-feira das 20:40 as 21:40, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Kayran)

Sexta-feira das 18:30 as 21:30, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Kayran)

Segunda-feira das 17:00 as 19:00, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Pedro)

Terça-feira das 17:00 as 19:00, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Pedro)

Quinta-feira das 17:00 as 19:00, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Pedro)

Sexta-feira das 17:00 as 19:00, Instituto de Ciência Exatas e Biológicas – ICEB

Turma 21 e 22 – Sala COM25 (LaPDI – ICEB I – final do corredor) – Monitoria (Pedro)

Ementa

Tipos abstratos de dados.

Noções de complexidade de algoritmos.

Recursividade.

Alocação dinâmica.

Estruturas de dados: listas, filas, pilhas e árvores.

Métodos de ordenação por comparação.

Métodos de pesquisa em memória primária.

Objetivos

Objetivos Gerais

O aluno deverá conhecer conceitos associados aos métodos de pesquisa e ordenação e de estruturas de dados de interesse teórico e prático.

Deverá também adquirir a capacidade de utilizar esses recursos pra desenvolvimento de programas, utilizando conceitos de modularização e abstração de dados.

Deverá ainda ser capaz de comparar estratégias de implementação do ponto de vista da complexidade dos algoritmos envolvidos, usando a notação O.

Programa

Apresentação do curso: programa, objetivos e bibliografia
Tipos de dados abstratos
Noções de análise de complexidade de algoritmos

Medida de Tempo de execução;
Análise assintótica, notação O.

Recursividade
Alocação dinâmica
Listas
Pilha e Fila
Filas de prioridade e implementação por heap
Árvores
Métodos de ordenação

selectsort, insertsort, bubblesort, shellsort, quicksort, heapsort e mergesort

Métodos de pesquisa

simples, binária, árvores binárias, digitais e AVL, e hashing

Bibliografia Básica

Ziviani N. e Botelho, F.C. Projetos de Algoritmos com implementação em C e Pascal (ou em Java e C++), Editora Thomson, 2003 (2007).

Tenenbaum, A.M., Langsam, Y. e Augenstein, M.J. Estruturas de Dados Usando C, Makron Books/Pearson Education, 1995.

Tenenbaum, A.M., Langsam, Y. e Augenstein, M.J. Data Strcutures Using C, Prentice-Hall International Editions, 1995.

Bibliografia Complementar

Cormen, T.H., Leiserson, C.E. Rivest, R.L. e Stein, C. Introduction to Algorithms. McGraw-Hill e The Mit Press, 2001.

Cormen, T.H., Leiserson, C.E. Rivest, R.L. e Stein, C. Algoritmos: Teoria e Prática. Editora Campus, Tradução da 2a. edição americana, 2001.

Knuth,D.E. The Art of Computer Programming. Vol 1: Fundamental Algorithms. Addison-Wesley, 3a. edição, 1997.

Knuth,D.E. The Art of Computer Programming. Vol 3: Sorting and Searching. Addison-Wesley, 1973.

Bibliografia Auxiliar

Mizrahi, V.V. Treinamento em Linguagem C, Pearson Prentice Hall, 2ª. edição, 2008.

Guimarães, A.M. e Lages, N.A.C. Algoritmos e Estruturas de Dados, LTC (Livros Técnicos e Científicos Editora LTDA), 21a Tiragem, 1994.

Farrer, H. Becker, C.G. Faria, E.C. Matos, H.F., Santos M.A., Maia, M.L. Algoritmos Estruturados, LTC (Livros Técnicos e Científicos Editora LTDA) 3ª. Edição, 1999.

Farrer, H. Becker, C.G. Faria, E.C. Campos-Filho, F.F. Matos, H.F., Santos M.A., Maia, M.L. Pascal Estruturado, LTC (Livros Técnicos e Científicos Editora LTDA) 3ª. Edição, 1999.

Lopes, Anita, Garcia, Guto, Introdução à Programação: 500 Algoritmos Resolvidos, Editora Campus, 2002.

Paulo Feofiloff, Algoritmos em linguagem C, Editora Campus, 2009.

Avaliação da Aprendizagem

Três testes: 6 pontos

Seis trabalhos práticos: 3 pontos

Entrega de listas de exercícios, trabalhos em aula prática/laboratório: 1 ponto

Exame especial: 10 pontos (substitui a nota integral do semestre)

Cronograma tentativo para 2º Semestre de 2009 (52 encontros – 36 teóricos e 16 práticos)

Encontro	P/T	Data	Dia Semana	Atividade
1	1P-T21	19/08/2009	Quarta-feira	Warm-up: operação com arquivos
2	1T	19/08/2009	Quarta-feira	Apresentação da Disciplina [slides] Teste Inicial para avaliar conhecimentos em Introdução à Programação (0,2 pontos extra)
1	1P-T22	20/08/2009	Quinta-feira	Warm-up: operação com arquivos
3	2T	20/08/2009	Quinta-feira	Aula 01 – Tipos de Dados Abstratos [slides] Lista 1 - Tipos Abstratos de Dados e Estruturas de Dados em C
4	3T	25/08/2009	Terça-feira	Reforço sobre algoritmos: manipulação de strings – presença não obrigatória
5	2P-T21	26/08/2009	Quarta-feira	Implementação de exercícios propostos (0,1 pontos extra) Implementação de exercício proposto sobre TAD
6	4T	26/08/2009	Quarta-feira	Aula 02 – Medida de Tempo de Execução de um Programa I [slides]
5	2P-T22	27/08/2009	Quinta-feira	Implementação de exercícios propostos (0,1 pontos extra) Implementação de exercício proposto sobre TAD
7	5T	26/08/2009	Quarta-feira	Reforço sobre algoritmos: ponteiros e funções – presença não obrigatória
8	6T	27/08/2009	Quinta-feira	Aula 02 – Medida de Tempo de Execução de um Programa I [slides]
9	3P-T21	02/09/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 1
9	3P-T22	03/09/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 1
10	7T	03/09/2009	Quinta-feira	Aula 02 – Medida de Tempo de Execução de um Programa I [slides]
11	8T	08/09/2009	Terça-feira	Reforço sobre algoritmos – presença não obrigatória
12	4P-T21	09/09/2009	Quarta-feira	Utilizando Latex para confecção dos trabalhos práticos
13	9T	09/09/2009	Quarta-feira	Aula 03 – Medida de Tempo de Execução de um Programa II [slides] Lista 2 – Limite Inferior
14	11T	09/09/2009	Quarta-feira	Solução de exercícios de complexidade – presença não obrigatória
12	4P-T22	10/09/2009	Quinta-feira	Utilizando Latex para confecção dos trabalhos práticos
15	10T	10/09/2009	Quinta-feira	Aula 04 – Medida de Tempo de Execução de um Programa III [slides] Lista 3 – Ordem de Complexidade
16	5P-T21	16/09/2009	Quarta-feira	Dúvidas Listas 1 e 2
17	13T	16/09/2009	Quarta-feira	Aula 05 – Medidas de Tempo de Execução [slides] Lista 4 – Função de Complexidade
18	12T	16/09/2009	Quarta-feira	Reforço sobre algoritmos – presença não obrigatória
16	5P-T22	17/09/2009	Quinta-feira	Dúvidas Listas 1 e 2
19	14T	17/09/2009	Quinta-feira	Aula 06 – Recursividade [slides] Lista 5 – Recursividade
20	6P-T21	23/09/2009	Quarta-feira	Dúvidas Listas 3, 4, 5 e 6
21	15T	23/09/2009	Quarta-feira	Aula 07 – Alocação Dinâmica [slides] Lista 6 – Alocação Dinâmica
22	16T	23/09/2009	Quarta-feira	Revisão para prova – presença não obrigatória
21	6P-T22	24/09/2009	Quinta-feira	Dúvidas Listas 3, 4, 5 e 6
23	17T	24/09/2009	Quinta-feira	1o. Teste – 2,0 pontos
24	7P-T21	30/09/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 2
25	18T	30/09/2009	Quarta-feira	Aula 08 – Listas Arranjos [slides] Lista 7 – Listas implementadas por Arranjos
24	7P-T22	01/10/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 2
26	19T	01/10/2009	Quinta-feira	Aula 9 e 10 – Listas Encadeadas [slides] Lista 8 – Listas implementadas por Encadeamento
27	8P-T21	07/10/2009	Quarta-feira	Lista 8 – Listas implementadas por Encadeamento – exercícios 1, 3, 5, 7, 9, 11 e 13
28	20T	07/10/2009	Quarta-feira	Aula 11 – Pilha [slides] Lista 9 – Pilha
27	8P-T22	08/10/2009	Quinta-feira	Lista 8 – Listas implementadas por Encadeamento – exercícios 2, 4, 6, 8, 10, 12 e 14
29	21T	08/10/2009	Quinta-feira	Aula 12 – Fila [slides] Lista 10 – Fila
30	9P-T21	14/10/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 3
30	9P-T22	15/10/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 3
31	10P-T21	21/10/2009	Quarta-feira	Lista 10 – Fila
32	22T	21/10/2009	Quarta-feira	Aula 13 – Árvore [slides] Lista 11 – Árvores
31	10P-T22	22/10/2009	Quinta-feira	Lista 10 – Fila
33	23T	22/10/2009	Quinta-feira	Aula 14 – Ordenação I – SelectSort, InsertSort, BubbleSort [slides]
34	11P-T21	28/10/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 4
35	24T	28/10/2009	Quarta-feira	Aula 15 – Ordenação II – ShellSort [slides]
34	11P-T22	29/10/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 4
36	25T	29/10/2009	Quinta-feira	Aula 16 – Ordenação III – QuickSort [slides]
37	12P-T21	04/11/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 5
38	26T	04/11/2009	Quarta-feira	Aula 17 – Ordenação IV – HeapSort [slides] Lista 12 – Ordenação
37	12P-T22	05/11/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 5
39	27T	05/11/2009	Quinta-feira	Aula 18 – Ordenação V – MergeSort [slides]
40	13P-T21	11/11/2009	Quarta-feira	Lista 11 – Árvore – exercícios 2, 4, 6, 8, 10, 12 e 14
41	28T	11/11/2009	Quarta-feira	Aula 19 – Pesquisa I – Pesquisa Sequencial & Binária [slides]
40	13P-T22	12/11/2009	Quinta-feira	Lista 11 – Árvore – exercícios 2, 4, 6, 8, 10, 12 e 14
42	29T	12/11/2009	Quinta-feira	2o. Teste – 2,0 pontos
43	14P-T21	18/11/2009	Quarta-feira	Dúvidas sobre Trabalho Prático 6
44	30T	18/11/2009	Quarta-feira	Aula 20 – Pesquisa II – Árvores Binária de Busca [slides]
43	14P-T22	19/11/2009	Quinta-feira	Dúvidas sobre Trabalho Prático 6
45	31T	19/11/2009	Quinta-feira	Aula 21 – Pesquisa III – Árvores Binária de Busca [slides]
46	15P-T21	25/11/2009	Quarta-feira	Implementação de Pesquisa Sequencial & Binária + Árvores Binária de Busca
47	32T	25/11/2009	Quarta-feira	Aula 22 – Pesquisa IV – Árvores AVL I [slides]
46	15P-T22	26/11/2009	Quinta-feira	Implementação de Pesquisa Sequencial & Binária + Árvores Binária de Busca
48	33T	26/11/2009	Quinta-feira	Aula 23 – Pesquisa V – Árvores AVL II [slides]
49	16P-T21	02/12/2009	Quarta-feira	Dúvidas TP6
50	34T	02/12/2009	Quarta-feira	Aula 24 – Pesquisa VIII – Árvores Digitais [slides]
49	16P-T22	03/12/2009	Quinta-feira	Dúvidas TP6
51	35T	03/12/2009	Quinta-feira	Aula 25 – Pesquisa VII – Hashing [slides] Lista 13 – Pesquisa
52	36T	10/12/2009	Quinta-feira	Dúvidas
53	37T	16/12/2009	Quarta-feira	3o. Teste – 2,0 pontos
54	38T	23/12/2009	Quarta-feira	Exame Especial – 10 pontos

Trabalhos Práticos

Trabalho Prático 1 – 0,5 pontos - entrega 15/09/2009

Trabalho Prático 2 – 0,5 pontos - entrega 06/10/2009 – Trabalhos Selecionados – [ solução 1 (Gustavo) / solução 2 (Luiz Henrique) ]

Trabalho Prático 3 – 0,5 pontos - entrega 20/10/2009 – Trabalhos Selecionados – [ solução 1 (Braúlio) / solução 2 (Cecília) / solução 3 (Luiz Henrique) / solução 4 (Vítor) ]

Trabalho Prático 4 – 0,5 pontos - entrega 03/11/2009 – Trabalhos Selecionados – [ solução 1 (Angelo) / solução 2 (Luiz Henrique) ]

Trabalho Prático 5 – 0,5 pontos - entrega 19/11/2009 – Trabalhos Selecionados – [ solução 1 (Cecília) / solução 2 (Johnnatan) / solução 3 (Luiz) ]

· [codigo]

Trabalho Prático 6 – 0,5 pontos - entrega 10/12/2009 – Trabalhos Selecionados – [ solução 1 (Braúlio) / solução 2 (Rafael) / solução 3 (Vítor)]

Listas de exercícios (CIC102)

Lista 1 - Tipos de Dados Abstratos e Estruturas de Dados em C [gabarito]

Lista 2 – Limite Inferior

Lista 3 – Ordem de Complexidade

Lista 4 – Função de Complexidade

Lista 5 – Recursividade

Lista 6 – Alocação Dinâmica

Lista 7 – Listas implementadas por Arranjos