SCC-201(Moacir)

Informações Gerais

Título: Introdução à Ciência de Computação II (SCC-201) - Bacharelado em Ciências de Computação

Professor: Moacir Ponti Jr (moacir at icmc usp br)

Aluna PAE: Pâmela Michele Cândida (pamela at icmc usp br; sala 1-008)

Monitor especial: Gabriel Coelho (amorimdecoelho at gmail com)

• Monitoria especial na sala 3-009 às quintas-feiras das 19h20 as 21h00

Horário de Aulas
segundas e quartas das 08h10 às 09h50 (sala 4-001)

Horários de Atendimento

Professor: segundas 13-15h, sextas 18-19h (sala 4-117)

Aluna PAE: segunda das 17h30 às 19h00 (sala 4-001)

dúvidas nos trabalhos, marcar horário por e-mail.

monitoria dia 18/10, para discutir trabalho 1, a partir das 17h00 ***apenas para alunos com nota final >= 5.0***

Programa

• Análise de algoritmos
• Recursividade (e relações de recorrência)
• Algoritmos de ordenação em memória interna
• Algoritmos de busca em memória interna
• Hashing (espalhamento) em memória interna
• Paradigmas de projeto de algoritmos

Cronograma Preliminar (com datas de provas e de entrega de trabalhos) *sujeito a alterações (atualizado em 10/11)

Provas: 25/08 (P1), 25/10 (P2) e 06/12 (P3)

Material Didático

- Apresentação da Disciplina

1. Análise de Algoritmos - parte 1
2. Análise de Algoritmos - parte 2
3. Análise de Algoritmos - parte 3
4. Recursão
5. Análise de Algoritmos - parte 4
6. Métodos de Ordenação em Memória Interna - parte 1
7. Métodos de Ordenação em Memória Interna - parte 2 (quicksort)
8. Métodos de Ordenação em Memória Interna - parte 3
9. Métodos de Ordenação em Memória Interna - parte 4
10. Métodos de Ordenação em Memória Interna - parte 5
11. Métodos de Ordenação em Memória Interna - parte 6
12. Busca sequencial (diversas), binária e interpolada
13. Hashing - parte 1
14. Hashing - parte 2
15. Projeto de Algoritmos

Códigos-fonte das aulas 8, 9, 10 e 11: Códigos-fonte

Site interessante que ilustra o funcionamento de algoritmos de ordenação: http://www.sorting-algorithms.com/

Vídeo com o "som" produzido pelos algoritmos de ordenação: http://youtu.be/t8g-iYGHpEA

Ver exemplos em código-fonte no site: http://sites.google.com/site/moacirponti/ seção "Teaching (aulas)"

Trabalhos Práticos

Os trabalhos serão submetidos apenas pelo sistema de submissão automática de trabalhos:

[Link para submissão dos trabalhos via SQTPM ]

Atenção: a saída do seu programa deverá ser exatamente como exemplificado no enunciado do trabalho, pois o sistema irá comparar apenas as saídas geradas. Antes de submeter, retire mensagens ao usuário, espaços, tabulações ('\t') e quebras de linha extras ('\n').

Critérios de avaliação

1. Solução correta pela representação de entrada e saída dos dados
2. Bom uso dos recursos do sistema (memória)
3. Prática de modularização e uso de funções
4. Clareza, endentação e uso de comentários

Trabalhos

0. Recursividade (teste do SQTPM) - aberto de 14/08 a 24/08

1. Algoritmos de Ordenação (A): entrega até 06/10 para pamela at icmc.usp.br

• Enunciado (pdf) versao nova, corrigida em 15/09
• Casos de Teste (tar.gz) versao nova, corrigida em 15/09

2. Algoritmos de Ordenação (B): Entrega pelo SQTPM de 03/11 até 11/11.

• Enunciado (pdf) versao nova em 27/10
• Caso de Teste (tar.gz)

3. Hashing: Entrega pelo SQTPM de 26/11 até 29/11

• Enunciado (pdf) <- atualizado em 22/11 foi modificado o número máximo de palavras (10000) e caracteres (512).
• Casos de Teste (tar.gz) <- atualizado em 18/11

Desenvolvam os seus próprios arquivos com casos de teste adicionais, prevendo diferentes situações

3. Trabalho Substitutivo: Entrega pelo SQTPM de 03/12 até 06/12.

• esse trabalho substitui a menor nota obtida entre os trabalhos, mesmo que a nota NTSUB < min{NT1,NT2,NT3}

• Enunciado (pdf)
• Casos de Teste (tar.gz)

Desenvolvam os seus próprios arquivos com casos de teste adicionais, prevendo diferentes situações

Listas de Exercícios

1. Análise de Algoritmos
2. Recursividade
3. Relação de Recorrência
4. Algoritmos de Ordenação (A) (atualizada em 13/09/2010 15/09/2010)
5. Algoritmos de Ordenação (B)
6. Busca
7. Hashing + Projeto de Algoritmos

Notas

• Planilha de notas e faltas completa (Atualizada em 23/11)

Bibliografia

• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Campus. 2002.
• ZIVIANI, N. Projeto de algoritmos: com implementações em Pascal e C. 2.ed., Thomson, 2004.
• FEOFILOFF, P. Projeto de algoritmos, Campus, 2008.
• FEOFILOFF, P. Projeto de algoritmos: em C, Disponível em: http://www.ime.usp.br/~pf/algoritmos/.

Leituras complementares

• FEOFILOFF, P. Minicurso de Análise de Algoritmos, 2010. Disponível em: http://www.ime.usp.br/~pf/livrinho-AA/.
• DOWNEY, A.B. Analysis of algorithms (Cap. 2), em: Computational Modeling and Complexity Science. Disponível em: http://www.greenteapress.com/compmod/html/book003.html.
• KNUTH, D. The Art of Computer Programming, vol.3: sorting and searching, 2.ed. Addison-Wesley, 1998.
• KNUTH, D. Selected Papers on Analysis of Algorithms, CSLI Lecture Notes, n.102, 2000.
• SCHILD, H. C Completo e Total, 3.ed. Pearson, 1997.