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. Notas P3
3. Notas e média de prova
4. Notas atualizadas, adicionais, média e frequência, mesma senha do arquivo anterior
5. Revisão de provas 2 e 3 dia 03/07, 10-12, sala 3-102 (ICMC - CAMPUS I)
6. Revisão pode ser feita em outro dia também, até no início do próximo semestre.
7. rec de prova na primeira semana de aula do próximo semestre. Data, hora (período noturno) e local a serem divulgados aqui.
8. o aluno deve passar na rec de trabalho para fazer a rec de prova, no caso de quem ficou de rec nas duas modalidades (prova e trabalho)

Sobre a Rec. dos Trabalhos (RT)

1. A média dos trabalhos (MT) será calculada sobre os 3 trabalhos com maior nota (o trabalho de menor nota será descartado).
2. Poderá fazer a RT quem ficar com 3.0 <= MT < 5.0
3. Durante a RT será liberado o acesso para cada trabalho x cuja nota NTx < 5.0
4. O objetivo da RT é conseguir nota >= 5.0 para cada NTx
   1. Caso os 4 trabalhos tenham NTx < 5.0, será apenas necessário resolver 3

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
2. Notas P3
3. Notas e média de prova
4. Notas dos Trabalhos

• Atenção: no Trabalho 3 houve diversos problemas com trabalhos copiados. Para mais detalhes procure o estagiário PAE.

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/