CIC102 – Algoritmos e Estruturas de Dados I
Carga Horária: 108 Horas (72h – Teórica / 36h – Prática)
Professor: David Menotti (menottid@gmail.com)
Monitor: Pablo Luiz Araújo Munhoz (pablo.munhoz@gmail.com)
1º Semestre
de 2009
Novidades
Exame especial - Verifique
sua situação - 08/07/2009 das 13:30 as 15:10 (02/07/2009 – 18:15)
Verifique sua nota
(02/07/2009 – 18:15)
Disponível notas do
quinto e sexto trabalhos práticos (02/07/2009 – 03:00)
Primeira tradução de mensagem do Trabalho
Prático 6 feita por Pedro R. M. Jr (0,2pts extra) (28/06/2009 – 20:00)
Correção no final do enunciado do Trabalho
Prático 6 (28/06/2009 – 15:30)
Corrigido link/url para a Lista
13 – Pesquisa – erro apontado por Matheus Silva (28/06/2009 – 14:00)
Correção no enunciado do Trabalho
Prático 6 (26/06/2009 – 12:00)
Disponível versões otimizadas dos
algoritmos (códigos)
do Trabalho Prático 5 (21/06/2009 – 23:22)
Verifique suas notas e frequencia
(19/05/2009 – 16:05)
Disponível texto,
gabarito
e notas
do teceiro teste (19/06/2009 – 18:40)
A aula teórica do dia
24/06 será no período noturno das 20:00 as 21:40 (19/06/2009 – 10:20)
O conteúdo dessa aula não será objetivo de avaliação do último
teste
Entrega de Trabalho
Prático 5 com bonus de 0,2pts adiado para 17/06/2009
Trabalho
Prático 6 disponível (14/06/2009 – 17:40)
Disponível notas do
segundo teste e quarto trabalho prático (13/06/2009 – 18:40)
Correção no código
para chamada de RadixSort do Trabalho Prático 5 (13/06/2009 – 12:00)
Correção/Melhoria no código
para visualização de resultados (log.txt) do Trabalho Prático 5 (12/06/2009 – 19:10)
Disponível melhores trabalhos
práticos 4 (12/06/2009 – 00:30)
Enfim, Trabalho
Prático 5 disponível [código]
(12/06/2009 – 00:15)
Segundo e talvez último adiamento de
Trabalhos Prático – Trabalho Prático 5 adiado para 23/06/2009 e +
Disponível melhores trabalhos
práticos 1, 2 e 3 (28/05/2009 – 20:20)
Verifique suas notas e frequencia
(28/05/2009 – 20:20)
Alteração no calendário – Haverá aula teórica no dia 10/06/2009 (28/05/2009 – 15:40)
Disponível texto
e gabarito
do segundo teste (20/05/2009 - 20:25)
Primeiro adiamento de Trabalhos
Prático – Trabalho
Prático 4 adiado para 26/05/2009 (13/05/2009 – 20:00)
Pequena correção no final do
enunciado do Trabalho
Prático 4 apontada por Kayran Santos (10/05/2009 – 08:50)
Alterações no enunciado e sugestões
(dicas) para o Trabalho Prático
4 (08/05/2009 – 15:30)
Trabalho
Prático 4 disponível (03/05/2009 – 17:15)
Disponível notas do
segundo trabalho prático (03/05/2009 – 2:00)
Pequena atualização no Trabalho
Prático 3 - +0,05pts extra para impressão frente-verso (01/05/2009 – 18:30)
Disponível notas do
primeiro trabalho prático (30/04/2009 – 17:10)
Disponível notas, texto
e gabarito
do primeiro teste (20/04/2009 - 15:40)
Atualização no horário de monitoria
(29/03/2009 – 14:00)
Trabalho
Prático 3 disponível (23/03/2009 – 20:30)
Pequena atualização no enunciado do Trabalho
Prático 1 (22/03/2009 – 11:30)
Trabalho
Prático 2 disponível (22/03/2009 – 11:30)
Atualização no enunciado do Trabalho
Prático 1 (19/03/2009 – 01:15)
Trabalho
Prático 1 disponível (15/03/2009 – 11:30)
Aulas de reforço começam hoje das
19:00 as 20:40 na sala 16 (ICEB I) (11/03/2009 – 16:00)
Cronograma tentativo disponível
(04/03/2009 – 12:30)
Horário:
Quarta-feira das 13:30 as 15:10,
Instituto de Ciência Exatas e Biológicas - ICEB
Turma 21 e 22 - Sala 16 (ICEB II) - Teórica
Quinta-feira das 15:20 as 17:00,
Instituto de Ciência Exatas e Biológicas - ICEB
Turma 21 e 22 - Sala 16 (ICEB II) – Teórica
Quarta-feira das 15:20 as 17:00,
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 17:00 as 18:40,
Instituto de Ciência Exatas e Biológicas – ICEB
Turma 21 e 22 – Sala COM22 (ICEB I)
– Monitoria
Quarta-feira das 15:20 as 18:50,
Instituto de Ciência Exatas e Biológicas - ICEB
Turma 21 e 22 – Sala COM22 (ICEB I) –
Monitoria
Quinta-feira das 17:00 as 18:40,
Instituto de Ciência Exatas e Biológicas - ICEB
Turma 21 e 22 – Sala COM22 (ICEB I)
– Monitoria
Sexta-feira das 13:30 as 17:00,
Instituto de Ciência Exatas e Biológicas - ICEB
Turma 21 e 22 – Sala COM22 (ICEB I)
– Monitoria
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.
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.
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
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.
Avaliação da Aprendizagem
Quatro testes: 6 pontos
Seis trabalhos práticos: 3 pontos
Dez trabalhos em aula
prática:/laboratório 1 ponto
Exame especial: 10 pontos (substitui
a nota integral do semestre)
Cronograma
tentativo para 1º Semestre de 2009 (54 encontros – 36 teóricos e 18 práticos)
Encontro |
P/T |
Data |
Dia Semana |
Atividade |
1 |
1T |
04/03/2009 |
Quarta-feira |
Apresentação da Disciplina [slides] Teste
Inicial para avaliar conhecimentos em Introdução à Programação (0,2 pontos extra) |
2 |
1P |
04/03/2009 |
Quarta-feira |
Turma 21 -
Implementação de exercícios
propostos (0,1 pontos extra) |
2 |
1P |
05/03/2009 |
Quinta-feira |
Turma 22 -
Implementação de exercícios
propostos (0,1 pontos extra) |
3 |
2T |
05/03/2009 |
Quinta-feira |
Aula 01 – Tipos de Dados Abstratos [slides] Lista
1 - Tipos Abstratos de Dados e Estruturas de Dados em C |
4 |
3T |
11/03/2009 |
Quarta-feira |
Aula 02 – Medida de Tempo de Execução de um Programa
I [slides] |
5 |
2P |
11/03/2009 |
Quarta-feira |
Turma 21 –
Implementação do exercício proposto na Aula
01 e outro |
6 |
4T |
11/03/2009 |
Quarta-feira |
Reforço sobre algoritmos – presença não obrigatória |
5 |
2P |
12/03/2009 |
Quinta-feira |
Turma 22 –
Implementação do exercício proposto na Aula
01 e outro |
7 |
5T |
12/03/2009 |
Quinta-feira |
Aula 03 – Medida de Tempo de Execução de um Programa
I [slides]
– a partir do slide 29 |
8 |
3P |
12/03/2009 |
Quinta-feira |
Reforço sobre algoritmos – presença não obrigatória |
9 |
6T |
18/03/2009 |
Quarta-feira |
Aula 04 – Medida de Tempo de Execução de um Programa
II [slides] |
10 |
4P |
18/03/2009 |
Quarta-feira |
Turma 21 –
Dúvidas sobre Trabalho
Prático 1 |
11 |
7T |
18/03/2009 |
Quarta-feira |
Reforço sobre algoritmos – presença não obrigatória |
10 |
4P |
19/03/2009 |
Quinta-feira |
Turma 22 –
Dúvidas sobre Trabalho
Prático 1 |
12 |
8T |
19/03/2009 |
Quinta-feira |
Aula 05 – Medida de Tempo de Execução de um Programa
III [slides] |
13 |
5P |
19/03/2009 |
Quinta-feira |
Reforço sobre algoritmos – presença não obrigatória |
14 |
9T |
25/03/2009 |
Quarta-feira |
Aula 06 – Medidas de Tempo de Execução [slides] |
15 |
6P |
25/03/2009 |
Quarta-feira |
Turma 21 –
Dúvidas Listas 1,2,3 e 4 |
15 |
6P |
26/03/2009 |
Quinta-feira |
Turma 22 –
Dúvidas Listas 1,2,3 e 4 |
16 |
10T |
26/03/2009 |
Quinta-feira |
Aula 07 – Recursividade [slides] |
17 |
11T |
01/04/2009 |
Quarta-feira |
Aula 08 – Recursividade [slides]
– a partir do slide 19 Resolução de Exercícios – Dúvidas Listas 1,2,3,4 e 5 |
18 |
7P |
01/04/2009 |
Quarta-feira |
Turma 21 –
Dúvidas sobre Trabalho
Prático 2 |
18 |
7P |
02/04/2009 |
Quinta-feira |
Turma 22 –
Dúvidas sobre Trabalho
Prático 2 |
19 |
12T |
02/04/2009 |
Quinta-feira |
Aula 09 – Alocação Dinâmica [slides] |
20 |
13T |
08/04/2009 |
Quarta-feira |
1o. Teste
– 1,8 pontos |
21 |
14T |
15/04/2009 |
Quarta-feira |
Aula 10 – Listas Arranjos [slides] |
22 |
8P |
15/04/2009 |
Quarta-feira |
Turma 21 –
Dúvidas sobre Trabalho
Prático 3 |
23 |
15T |
15/04/2009 |
Quarta-feira |
Reforço sobre algoritmos – presença não obrigatória |
22 |
8P |
16/04/2009 |
Quinta-feira |
Turma 22 –
Dúvidas sobre Trabalho
Prático 3 |
24 |
16T |
16/04/2009 |
Quinta-feira |
Aula 11 – Listas Encadeadas [slides] |
‘25 |
9P |
16/04/2009 |
Quinta-feira |
Reforço sobre algoritmos – presença não obrigatória |
26 |
17T |
22/04/2009 |
Quarta-feira |
Aula 12 – Listas Encadeadas [slides]
– a partir do slide 18 |
27 |
10P |
22/04/2009 |
Quarta-feira |
Turma 21 – Lista
8 – Listas implementadas por Encadeamento – exercícios 1, 3, 5, 7, 9, 11
e 13 |
27 |
10P |
23/04/2009 |
Quinta-feira |
Turma 22 – Lista
8 – Listas implementadas por Encadeamento – exercícios 2, 4, 6, 8, 10, 12
e 14 |
28 |
18T |
23/04/2009 |
Quinta-feira |
Aula 13 – Pilha [slides] |
29 |
19T |
29/04/2009 |
Quarta-feira |
Aula 14 – Fila [slides] |
30 |
11P |
29/04/2009 |
Quarta-feira |
Turma 21 –
Dúvidas sobre Trabalho Prático 4 |
30 |
11P |
30/04/2009 |
Quinta-feira |
Turma 22 –
Dúvidas sobre Trabalho Prático 4 |
31 |
20T |
30/04/2009 |
Quinta-feira |
Aula 15 – Árvore [slides] |
32 |
21T |
06/05/2009 |
Quarta-feira |
Aula 16 – Ordenação I – SelectSort, InsertSort,
BubbleSort [slides] |
33 |
12P |
06/05/2009 |
Quarta-feira |
Turma 21 – Lista
10 – Fila |
33 |
12P |
07/05/2009 |
Quinta-feira |
Turma 22 – Lista
10 – Fila |
34 |
22T |
07/05/2009 |
Quinta-feira |
Aula 17 – Ordenação II – ShellSort [slides] |
35 |
23T |
13/05/2009 |
Quarta-feira |
Apresentação do Trabalho Prático 3 |
36 |
13P |
13/05/2009 |
Quarta-feira |
Turma 21 – Lista
11 – Árvore – exercícios 1, 3, 5, 7, 9, 11 e 13 |
36 |
13P |
14/05/2009 |
Quinta-feira |
Turma 22 – Lista
11 – Árvore – exercícios 2, 4, 6, 8, 10, 12 e 14 |
37 |
24T |
14/05/2009 |
Quinta-feira |
Aula 18 – Ordenação III – QuickSort [slides] |
38 |
25T |
20/05/2009 |
Quarta-feira |
2o. Teste
– 1,8 pontos |
39 |
14P |
20/05/2009 |
Quarta-feira |
Turma 21 –
Implementação de SelectSort, InsertSort e BubbleSort |
39 |
14P |
21/05/2009 |
Quinta-feira |
Turma 22 –
Implementação de SelectSort, InsertSort e BubbleSort |
40 |
26T |
21/05/2009 |
Quinta-feira |
Aula 19 – Ordenação IV – HeapSort [slides] |
41 |
27T |
27/05/2009 |
Quarta-feira |
Aula 20 – Ordenação V – MergeSort [slides] |
42 |
15P |
27/05/2009 |
Quarta-feira |
Turma 21 –
Implementação de ShellSort, QuickSort |
42 |
15P |
28/05/2009 |
Quinta-feira |
Turma 22 –
Implementação de ShellSort, QuickSort |
43 |
28T |
28/05/2009 |
Quinta-feira |
Aula 22 – Pesquisa I – Pesquisa Sequencial &
Binária [slides] |
44 |
29T |
03/06/2009 |
Quarta-feira |
Aula 23 – Pesquisa II – Árvores Binária de Busca [slides] |
45 |
16P |
03/06/2009 |
Quarta-feira |
Turma 21 –
Dúvidas sobre Trabalho Prático 5 |
45 |
16P |
04/06/2009 |
Quinta-feira |
Turma 22 –
Dúvidas sobre Trabalho Prático 5 |
46 |
30T |
04/06/2009 |
Quinta-feira |
Aula 23 – Pesquisa II – Árvores Binária de Busca [slides] |
47 |
31T |
10/06/2009 |
Quarta-feira |
Aula 24 – Pesquisa III – Árvores AVL I [slides] |
48 |
17P |
17/06/2009 |
Quarta-feira |
Turma 21 -
Implementação de Pesquisa Sequencial & Binária + Árvores Binária de Busca |
48 |
17P |
18/06/2009 |
Quinta-feira |
Turma 22 -
Implementação de Pesquisa Sequencial & Binária + Árvores Binária de Busca |
49 |
32T |
18/06/2009 |
Quinta-feira |
3o. Teste
– 1,2 pontos |
50 |
33T |
24/06/2009 |
Quarta-feira |
Aula 27 – Pesquisa VI – Hashing [slides]
– à noite |
51 |
34T |
25/06/2009 |
Quinta-feira |
Aula 26 – Pesquisa V – Árvores Digitais (Trie e
Patricia) [slides] |
52 |
35T |
01/07/2009 |
Quarta-feira |
Aula 25 – Pesquisa IV – Árvores AVL II [slides] |
53 |
18P |
01/07/2009 |
Quarta-feira |
Turma 21 –
Implementação de Árvores AVL ( |
53 |
18P |
02/07/2009 |
Quinta-feira |
Turma 22 –
Implementação de Árvores AVL ( |
54 |
36T |
02/07/2009 |
Quinta-feira |
4o. Teste
– 1,2 pontos |
55 |
37T |
08/07/2009 |
Quarta-feira |
Exame
Especial – 10 pontos |
|
|
09/07/2009 |
Quinta-feira |
Apresentação dos resultados |
Trabalhos Práticos
Trabalho
Prático 1 – 0,5 pontos - entrega 31/03/2009 – Trabalhos Selecionados – [ sol 1
(Lincoln) / sol 2
(Daniel) / sol 3
(Pedro Ismar) / sol 4
(Pedro Ribeiro) ]
Trabalho
Prático 2 – 0,5 pontos - entrega 21/04/2009 – Trabalhos Selecionados – [ solução 1
(Alex) / solução 2
(Suellen) ]
Trabalho
Prático 3 – 0,5 pontos - entrega 05/05/2009 – Trabalhos Selecionados – [ solução 1
(Kayran) ]
Trabalho
Prático 4 – 0,5 pontos - entrega 26/05/2009 – Trabalhos Selecionados – [ solução 1
(Filipe) / solução 2
(Pedro Ismar) / solução 3
(Suellen) / solução 4
(Kayran) ]
Trabalho
Prático 5 – 0,5 pontos - entrega 23/06/2009 – Trabalhos Selecionados – [
solução 1 (???) / solução 2 (???) ]
·
[codigo]
Trabalho
Prático 6 – 0,5 pontos - entrega 30/06/2009 – Trabalhos Selecionados – [
solução 1 (???) / solução 2 (???) ]
Listas de exercícios (CIC102)
Lista
1 - Tipos de Dados Abstratos e Estruturas de Dados em C [gabarito]
Lista
3 – Ordem de Complexidade
Lista
4 – Função de Complexidade
Lista
7 – Listas implementadas por Arranjos
Lista
8 – Listas implementadas por Encadeamento
Listas
de exercícios para fortalecimento de Introdução à Programação (CIC100)
1ª.
Lista de Exercícios – Entrada/Saída, Atribuição e Estrutura Seqüencial (35
exercícios, 7 para cada aluno) [solução]
[professor]
2ª.
Lista de Exercícios – Estrutura Condicional (44 exercícios, 11 para cada aluno)
[solução]
[professor]
3ª.a
Lista de Exercícios – Estrutura de Repetição (100 exercícios, 20 para cada
aluno) [solução]
[professor]
3ª.b
Lista de Exercícios – Estrutura de Repetição (100 exercícios, 20 para cada
aluno) [solução]
[professor]
4ª.
Lista de Exercícios – Estruturas de Dados Compostas Homogêneas Unidimensionais
– Vetores (35 exercícios, 7 para cada aluno) [solução]
[professor]
5ª.
Lista de Exercícios – Estruturas de Dados Compostas Homogêneas
Multidimensionais – Matrizes (30 exercícios, 6 para cada aluno) [solução]
[professor]
6ª.
Lista de Exercícios – Modularização – Funções e Procedimentos (30
exercícios, 6 para cada aluno) [solução]
[professor]
Recursos
Softwares
Dev C++
Moodle - http://www.decom.ufop.br/
Apostilas C:
Renato
Cardoso Mesquita - DEE/UFMG
Camillo
- PUCPR
GACLI
- UNICAMP
Menotti
– DCC/UFMG
Aprenda
Microsoft Visual C++ 5.0 em 24 horas (texto público, em inglês)
Apostilas e documentos para LATEX
Símbolos
em Latex – 105 páginas de caracteres e símbolos especiais
A
não tão pequena introdução ao Latex – 132 páginas – aprenda de tudo um
pouco
Uma não
tão pequena introdução ao Latex – 132 páginas – aprenda de tudo um pouco