Algoritmos e Estrutura de Dados [if969]

Semestre Letivo 2012.1

Local: Centro de Informática, horários: segunda (17:00-18:40), sala D-002 e quarta (18:50-20:30), Lab5.

Sistema Corretor:

Endereço do sistema corretor para submissão de exercícios:

Atenção:

Esta comunidade contém apenas notas de aulas superficiais. Estas notas não devem ser utilizadas como livro-texto. Um bom desempenho na disciplina depende muito do estudo mais profundo dos livros e, principalmente, da prática no computador.

Ementa:

Ensinar os conceitos básicos de algoritmos; algoritmos e estruturas de dados dinâmicas básicas; técnicas de construção de algoritmos; conceitos de complexidade de algoritmo. Este curso visa trabalhar principalmente introdução a algoritmos e estruturas de dados, incluindo projeto, análise e implementação na linguagem Java.

Apoio

  • Arley Ramalho Rodrigues Ristar (arrr2)
  • Lairson Emanuel Rodrigues de Alencar Oliveira (lerao)
  • Juliandson Estanislau Ferreira (jef)
  • Marcela Pereira de Oliveira (mpo)

Bibliografia sugerida:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronaldo L.; Stein, Clifford; Introduction to Algorithms – Third Edition, MIT Press, 2009. [Supplemental Content] [google books]

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronaldo L.; Stein, Clifford; Algoritmos: teoria e prática: tradução da 2ª edição [americana], Vandenberg D. de Souza, Ed. Campus, 2002. ISBN 85-352-0926-3. [buscapé]

Bibliografia Complementar:

  • Introduction to the Java Collections Framework (ótimo tutorial da Sun sobre coleções, não deixe de ler).
  • Michael T. Goodrich & Roberto Tamassia. Estruturas de Dados e Algoritmos em Java. 4ª edição. Ed. Bookman, 2007 – ISBN 9788560031504 [Google Books]
  • TENENBAUM, A. M.; LANGSAN, Y.; AUGENSTEIN, M. J. Estruturas de Dados Usando C. São Paulo: Makron Books, 1995.
  • ZIVIANI, Nivio. Projeto de Algoritmos. Editora Nova Fronteira, 2004.
  • SEDGEWICK, Robert. Algorithms in C++. Addison Wesley, 2000.
  • MANBER, Udi. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989.
  • SEDGEWICK, Robert. and Flajolet, Philippe. An Introduction to the Analysis of Algorithms. Addison Wesley, 1996.
  • How to Think Like a Computer Scientist – Python Version [link]

Boas Práticas:

  • A. Hunt, D. Thoma,. The Pragmatic Programmer, Addison Wesley, 2000
  • A. Oram, G. Wilson, Beautiful Code, O’Reilly, 2007
  • R. C. Martin, Clean Code, Prentice Hall, 2009

Web:

  • Introduction to Algorithms, Third Edition Supplemental Content [link]
  • Data Structures and Algorithms in Java(4th edition) [link]
  • Apostila POO – Java – Eclipse [link]
  • Livro Virtual de Estruturas de Dados do prof. Prof. Dr. Roberto Ferrari – UFSCar [link do site]
  • JEDI (Java Education and Development Initiative) – DFJUG – Módulo 3: Estrutura de Dados [link do curso]
  • MIT OpenCourseWare – 6.006 Introduction to Algorithms, Spring 2008 [link do curso]
  • Algorithm Education in Python [link]
  • Invent Your Own Computer Games with Python [link]
  • Aprenda Computação com Python [link]

Lista de emails:

Software:

Para o aprendizado do conteúdo da disciplina, é fundamental que os alunos pratiquem programação de computadores. Para tanto, é necessário instalar um ambiente de desenvolvimento Java. Esta página disponibiliza 2 ambientes de desenvolvimento distintos:

Avaliação:

Mini-provas – Programação

Mini-provas anteriores – 2011.2

  1. Mini-prova 01 [link] – release: 01/09, data de entrega: 16/09, 12:00
  2. Mini-prova 02 [link] – release: 19/09, data de entrega: 02/10, 23:59
  3. Mini-prova 03 [link] – release: 06/10, data de entrega: 19/10, 23:59
  4. Mini-prova 04 [link] – release: 24/10, data de entrega: 02/11, 23:59
  • Planilha de Acompanhamento detalhado das Mini-Provas 2011.2 [link]

Provas anteriores

Projetos

  • Página dos projetos de 2011.1 [link]
  • Página dos projetos de 2011.2 [link]
  • Página dos projetos de 2012.1 [link]

Aulas práticas (créditos profa. Katia Silva Guimarães – IF672 – Algoritmos e Estruturas de Dados)

  • É terminantemente proibido o uso de imports no código;
  • Evitem usar readchar(), readline() e print(“n”) em Java;
  • Vocês devem apenas se preocupar nas entradas em ler números e strings;
  • Arquivos (Entrada e Saída) em Java [transparências]
  • Download da classe Arquivo.java [link]

Plano de aulas:

| —– | | Aula | Data | Local | Descrição | Anexos | | 1 | 05/03 | | Apresentação dos Objetivos da Disciplina [link] e Conceitos básicos de programação Java [link] | – Sugestão: The Design Patterns Page [link] | | 2 | 07/03 | | Projeto Orientado a Objetos em Java [link] | | | 3 | 12/03 | | Aula de Revisão de Java | – Sugestão: listas de exercício 1 [link] e 2 [link]
– Exercício 01 – String de conexão [link] | | 4 | 14/03 | | Fundamentação: Algoritmos, para que servem? [link] | – Sugestão: Leitura dos capítulos 1 e 2 do livro do Cormen
– InsertionSort (python) [link] | | 5 | 19/03 | | Notações [link] e Recorrência [link] | – Sugestão: Leitura dos capítulos 3 e 4 do livro do Cormen | | 6 | 21/03 | Lab | Exercícios Práticos de Revisão – Lista #0 | | | 7 | 26/03 | | Algoritmos de Ordenação: Heap Sort [link] | – Atenção: Exercícios no último slide
– Revisão: Ordenação: Bubble Sort; Selection Sort; Insertion Sort; Merge Sort [link]
– Sugestão: Leitura do Capítulo 6 do livro do Cormen & Hints for implementing HeapSort & Priority Queues in Python [link]
– HeapSort (python) [link] | | 8 | 28/03 | | Algoritmos de Ordenação: Quick Sort [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 7 do livro do Cormen
– QuickSort (python) [link]
– RandomizedQuickSort (python) [link] | | 9 | 02/04 | | Exercícios Práticos de Revisão – Lista #01 | | | 10 | 04/04 | | Estrutura de Dados Lista [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 10 do livro do Cormen
– Na web: JVALL: Java Automated Linked List
– TAD List e TAD Node (python) [link]
– Driver para teste da TAD List (python) [link] | | 11 | 09/04 | | Estrutura de Dados Pilha e Fila [link] | – Atenção: Exercícios nos últimos slides
– Sugestão: Leitura do Capítulo 10 do livro do Cormen
– Na web: Demonstração de Pilha por LSE (by UC Prof. John Franco)[link]
– TAD Pilha (python) [link]
– Driver para teste da TAD Pilha (python) [link] | | 12 | 11/04 | | Tabelas Hash (Parte I) [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 11 do livro do Cormen | | 13 | 16/04 | Lab | Exercícios Práticos de Revisão – Lista #02 | | | 14 | 18/04 | | Tabelas Hash (Parte II) [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 11 do livro do Cormen | | 15 | 23/04 | | Aula de Revisão | | | 16 | 25/04 | | Primeiro Exercício Escolar | | | 17 | 07/05 | Lab | Prova Prática – Lista #03 | | | 18 | 09/05 | | Estruturas de Dados Árvores Genéricas [link] e Binárias [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 10 (Seção 4) e 12 do livro do Cormen
– Na web: Demonstração de árvore genérica (by UC Prof. John Franco)[link]; Busca em Árvores Binárias [link]; Árvores invertidas [link]; Árvores Binárias de Pesquisa [link]; Inserção e remoção em Árvores Binárias [link]
– TreeNode (python) [link]
– Tree (python) [link]
– DriverTrees (python) [link] | | 19 | 14/05 | | Estruturas de Dados Árvores AVL [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 12 do livro do Cormen
– Na web: Demonstrações (by UC Prof. John Franco): Inserção/remoção em árvores AVL [link]; Rotação trinodo [link] | | 20 | 16/05 | | Estruturas de Dados Árvores Red-Black [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 13 do livro do Cormen
– Na web: Demonstrações (by UC Prof. John Franco): Inserção/remoção em árvores rubro-negras [link] [código]
– Árvore rubro-negra (Wikipedia)
– Red/Black Tree Demonstration (link)
– Red-Black Trees Animation(link)
RBTree.py The Red/Black Trees Module
RedBlack Balanced Tree Searching and Sorting Library by Damian Ivereigh
Red black tree (Python recipe) | | 21 | 21/05 | | Estruturas de Dados Grafo: Introdução [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 22 do livro do Cormen | | 22 | 23/05 | | Estruturas de Dados Grafo: Busca em Profundidade [link] e em Largura [link] | – Atenção: Exercícios no último slide
– Sugestão: Leitura do Capítulo 22 do livro do Cormen | | 23 | 28/05 | | Complexidade e Completude [link] | – Sugestão: Leitura do Capítulo 34 do livro do Cormen | | 24 | 30/05 | | ___Exercícios Práticos de Revisão – Lista #04_ | | | 25 | 04/06 | | Acompanhamento do Projeto | | | 26 | 06/06 | | Acompanhamento do Projeto | | | 27 | 11/06 | | Acompanhamento do Projeto | | | 28 | 13/06 | | Acompanhamento do Projeto | | | 29 | 18/06 | | **Segundo Exercício Escolar** | | | 30 | 20/06 | | **Apresentação do Projeto** | | | 31 | 25/06 | | **Prova Final + 2ª Chamada** | |

Curtir isso:

Curtida Carregando…