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 +0,2 pts para entrega até 16/06/2009 (10/06/2009 – 14:00)

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.

 

Programa

 

  1. Apresentação do curso: programa, objetivos e bibliografia
  2. Tipos de dados abstratos
  3. Noções de análise de complexidade de algoritmos
    • Medida de Tempo de execução;
    • Análise assintótica, notação O.
  4. Recursividade
  5. Alocação dinâmica
  6. Listas
  7. Pilha e Fila
  8. Filas de prioridade e implementação por heap
  9. Árvores
  10. Métodos de ordenação
    • selectsort, insertsort, bubblesort, shellsort, quicksort, heapsort e mergesort
  11. 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.

 

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]

Lista 2 – Limite Inferior

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]

Lista 3 – Ordem de Complexidade

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]

Lista 4 – Função de Complexidade

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]

Lista 5 – Recursividade

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]

Lista 6 – Alocação Dinâmica

20

13T

08/04/2009

Quarta-feira

1o. Teste – 1,8 pontos

21

14T

15/04/2009

Quarta-feira

Aula 10 – Listas Arranjos [slides]

Lista 7 – Listas implementadas por Arranjos

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

Lista 8 – Listas implementadas por Encadeamento

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]

Lista 9 – Pilha

29

19T

29/04/2009

Quarta-feira

Aula 14 – Fila [slides]

Lista 10 – Fila

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]

Lista 11 – Árvores

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]

Lista 12 – Ordenação

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]

Lista 13 – Pesquisa

53

18P

01/07/2009

Quarta-feira

  Turma 21 – Implementação de Árvores AVL (0,1 pts)

53

18P

02/07/2009

Quinta-feira

  Turma 22 – Implementação de Árvores AVL (0,1 pts)

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 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

Lista 8 – Listas implementadas por Encadeamento

Lista 9 – Pilha

Lista 10 – Fila

Lista 11 – Árvore

Lista 12 – Ordenação

Lista 13 – Pesquisa

 

 

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

Borland C

Dev C++

Moodle - http://www.decom.ufop.br/moodle/

Apostilas C:

Renato Cardoso Mesquita - DEE/UFMG

Camillo - PUCPR

GACLI - UNICAMP

MenottiDCC/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