SCC-603 2012

SCC-603 --- Algoritmos e Estruturas de Dados II --- 1º Semestre 2012 [ementa]

Professora: Rosane Minghim (rminghim at icmc.usp.br)

Horário de atendimento: Sextas-feiras 15:00 às 18:00

Sala: 4-206

Assistente PAE: Rafael Messias Martins (rmartins at icmc.usp.br)

Horário de atendimento: Segunda-feira, 19:00 às 21:00

Sala: 3-009

Avisos

1. Notas P2
2. Revisão de provas 2 e 3 amanhã, dia 03/07, 10-12, sala 3-102 (ICMC - CAMPUS I)
3. Notas da P3 saem hoje, 02/07
4. Revisão pode ser feita em outro dia também, até no início do próximo semestre.
5. rec na primeira semana de aula do próximo semestre. Data, hora (período noturno) e local a serem divulgados aqui.

Cronograma e Critérios de Avaliação

Cronograma e Avaliação

Material Didático

1. Arquivo 01 - Introdução a Grafos (Revisado)
2. Arquivo 02 - Grafos Algoritmos (Revisado)
3. Grafos - Caminhos (complementar)
4. Arquivo 03 - Grafos Caminhos Mínimos
5. Arquivo 04 - Organização de Arquivos (Revisado)
6. Arquivo 05 - Fundamentos de Arquivos (Revisado)
7. Fundamentos de Arquivos: Códigos-exemplo (complementar)
8. Arquivo 06 - Armazenamento Secundário, parte 1 (Revisado)
9. Arquivo 07 - Armazenamento secundário, parte 2 (Revisado)
10. Arquivo 08 - Processamento Cosequencial (Revisado)
11. Arquivo 09 - Índices - Cap. 5
12. Arquivo 11 - Árvores B, parte 1
13. Arquivo 12 - Árvores B, parte 2
14. Arquivo 13 - Árvores B, parte 3
15. Arquivo 14 - Árvores B, parte 4
16. Arquivo 15 - Árvores B+
17. Hashing

Trabalhos

O envio dos trabalhos será feito pelo SQTPM.

• Trabalho 0 - Demonstração do SQTPM
• Trabalho 1 - Menores Caminhos (Atualizado)
  • Prazo: 15/05 (Podem continuar submetendo; desconto de 0,5 ponto por dia)
• Trabalho 2 - Betweenness (Atualizado)
  • Prazo: 21/05
• Dicas:
  • Cuidado com a memória!
    • Não dupliquem vértices com dados, por exemplo o nome. Cada vértice só deve ter UMA cópia na memória a qualquer momento. Sempre que tiverem que referenciar esse vértice (numa aresta, por ex., ou numa lista de predecessores), usem um ponteiro ou um "id" inteiro, por ex.
    • Cuidado com alocação dinâmica; não se percam pelo mar de ponteiros que vocês mesmo criam. Gerenciem cada ponteiro com cuidado.
    • Lembrem-se: quando vocês tem informação prévia do tamanho da lista (e esse tamanho não muda), um array é muito melhor que uma lista encadeada. Ou seja: tendo o número N de vértices, porque não alocar um array de N posições e atribuir um "id" de 0 a N-1 para cada vértice? Assim vocês poderão acessar qualquer vértice em tempo O(1) com "array[id]".
  • Cuidado com o tempo!
    • Evitem buscas completas no grafo se não for estritamente necessário. Se você precisa fazer uma busca linear no grafo toda vez que um vértice é referenciado, algo está errado no seu algoritmo (ver dica anterior sobre o array).
    • Não usem campos como nome (string) para o "id" do vértice. Operações com strings não são eficientes e são complicadas de usar em C, devido à alocação dinâmica. Evitem ao máximo manipulação de strings nesse contexto.
• Trabalho 3 - Índices
• Trabalho 4 - Árvore B

Exercícios de Aula

1. Exercício 1 (05/03/12)

1. Exercício 2 (20/03/12)

Listas de Exercícios

1. Lista de Exercícios 1
2. Lista de Exercícios 2
3. Lista de Exercícios 3
4. Lista de Exercícios 4
5. Lista 5 - Processamento Cosequencial
6. Lista 6 - Estruturas de Arquivos

Notas

1. Notas P2

Sugestões de leitura

Livro: Como passar em provas e concursos.

• Autor: William Douglas.
• Link: http://bit.ly/y98WhW

Livro: Data Structures and Algorithms in C++/Java

• Autores: M. T. Goodrich e R. Tamassia
• Link: http://ww0.java4.datastructures.net/

Livro: Projeto de Algoritmos

• Autor: N. Ziviani
• Link: http://www.dcc.ufmg.br/algoritmos/

Livro: Introduction to Algorithms

• Autores: T. H. Cormen, C. E. Leiserson e R. L. Rivest
• Link: http://mitpress.mit.edu/algorithms/