Informações Gerais

Primeiro Semestre de 2017

  • Turmas Teóricas: Terças (CB15) e Sextas (CB02) às 10h

  • Laboratório: Sextas (SI03 e SI05) às 14h

  • Informações adicionais: PDF

Contatos
Atendimento

O horário de atendimento será prestado sempre depois das aulas pelo professor e pelos monitores durante o laboratório. Caso necessário, atendimentos extras podem ser combinados por e-mail.

Avisos

Sugestão As notas da P2 já estão online.

Datas Importantes

Provas

  • Primeira prova: 25/Abril/2017

  • Segunda prova: 23/Junho/2017

  • Exame: 11/Julho/2017

Laboratórios

  • Lab. 1: 03/04/2017 - Paciência

  • Lab. 2: 30/04/2017 - Pílulas de Nanicolina

  • Lab. 3: 30/05/2017 - Googol

  • Lab. 4: 18/06/2017 - O Jogo do Bacon!

Listas de Exercícios

Lista Extra - Substitutiva

Esta lista deverá ser entregue no máximo até dia 23/06 antes do início da prova.

Aviso Atenção: Essa lista de exercícios substituirá a nota de apenas um dos testes caso você tenha perdido. Não substituirá testes com nota zero.

Os exercícios a serem entregues são:

  • Lista 1.30

  • Lista 1.34

  • Lista 2.12

  • Lista 2.17

  • Lista 3.4

  • Lista 3.5

  • Lista 3.11

  • Lista 4.6

  • Lista 4.14

  • Lista 4.18

  • Lista 4.19

  • Lista 5.10

  • Lista 5.11

  • Lista 5.13

Laboratórios

Os laboratórios deverão ser entregues via Susy: https://susy.ic.unicamp.br:9999/mc202bc/

  • Lab. 1: Paciência

    • Enunciado: PDF

  • Lab. 2: Pílulas de Nanicolina

    • Enunciado: PDF

    • Código Auxiliar: bitstream.h

    • Versão Executável - Use como modelo para o seu código:

      • Linux: nanicolina
        Para executar, baixe o arquivo nanicolina, dê permissão de execução:
        $ chmod a+x nanicolina
        $ ./nanicolina

      • Windows: nanicolina.exe

    • Avaliação do Lab. 02: Por limitações do Susy, o Lab. 02 será avaliado individualmente pelos monitores. A submissão continua sendo pelo Susy! Contudo, o processo de correção não será imediato e feito pelo Susy como vocês estão acostumados. Existe um corretor automático (semelhante ao utilizado pelo Susy) que será empregado pelos monitores. Todos os arquivos de entrada de teste e o corretor automático estão disponíveis. Para utilizá-lo basta baixar o arquivo lab02_testes_abertos.zip, descompactá-lo, colocar o seu arquivo.c no mesmo diretório, e executar o script de correção. Assim, você pode testar o seu programa antes de fazer a submissão quantas vezes quiser.

  • Lab. 3: Googol

    • Enunciado: PDF

    • Aqui estão os resultados do desafio. As barras representam quantas vezes o programa é mais lento do que o programa mais rápido de todos ("Professor Karatsuba + Base Variável"). Por exemplo, a versão "Professor Simples" é 10,40X mais lenta que a versão mais elaborada. Dois alunos bateram o tempo do meu programa na versão simples (base 10) e na versão com Karatsuba!! Parabéns! Apenas as submissões que passaram em TODOS os testes do Susy estão abaixo. Os nomes dos alunos foram substituídos por AAA, BBB, … Se você quiser que seu nome apareça ou apenas quiser saber quem é você me mande um e-mail!

Ranking Lab. 03

  • Lab. 4: O Jogo do Bacon!

    • Enunciado: PDF

    • Implementação do professor:

      • Linux-64: bacon

      • Linux-32: bacon32

      • Windows-32: bacon.exe

        • Usei um compilador bem velho para Windows, então o desempenho é bem inferior ao das versões para Linux

    • Exemplos de entrada e saída: atores.exemplo, consulta.exemplo, saida.exemplo

      • Para executar basta fazer ./bacon atores.exemplo consulta.exemplo

    • Script para baixar dados do IMDB (Linux): baixa_e_processa_arquivos.sh

      • Infelizmente por motivos legais não posso colocar online os arquivos pré-processados.

Notas

Você encontra as notas neste link.

Aqui estão os critérios utilizados para a correção assim como os comentários para cada um dos laboratórios submetidos:
- Laboratório 02
- Laboratório 03
- Laboratório 04

Aulas

  • 03/03/2017 - Aula 1

    • Apresentação do curso e revisão relâmpago.

    • Slides: PDF

  • 07/03/2017 - Aula 2 - Listas ligadas - Parte 1 - Definição e operações básicas.

  • 10/03/2017 - Aula 3 - Listas ligadas - Parte 2 - Ordenação.

  • 14/03/2017 - Aula 4 - Listas ligadas - Parte 3 - Listas duplamente ligadas e listas circulares, Pilhas.

  • 17/03/2017 - Aula 5 - Pilhas (Continuação), Filas.

  • 21/03/2017 - Aula 6 - µ-revisão e Teste 1.

  • 24/03/2017 - Aula 7 - Comentários do Teste 1, Árvores Binárias Parte 1.

  • 28/03/2017 - Aula 8 - Árvores Binárias Parte 2.

  • 31/03/2017 - Aula 9 - Árvores Binárias Conclusão, Jogo dos Animais

    • Códigos: Versão Chutadora (RUIM), Versão Inquisitiva (BOA).
      Note que nenhuma das implementações está completa. No final do jogo a memória não é liberada.
      Exercício: Modifique o código para liberar a memória alocada para cada um dos nós da árvore.

  • 04/04/2017 - Aula 10 - Filas com prioridade (heaps) e Heapsort.

  • 07/04/2017 - Aula 11 - Heaps Parte 2, Teste 2

  • 11/04/2017 - Aula 12 - Heaps Final, Árvores Binárias de Busca

  • 14/04/2017 - Não haverá aula - Sexta-feira Santa

  • 18/04/2017 - Aula 13 - Árvores Binárias de Busca Parte 2, Revisão para prova

  • 21/04/2017 - Não haverá aula - Tiradentes

  • 25/04/2017 - Aula 14 - Prova 1

  • 28/04/2017 - Aula 15 - Plantão de dúvidas

  • 02/05/2017 - Aula 16 - Árvores Binárias Balanceadas de Busca

  • 05/05/2017 - Aula 17 - Árvores Rubro-Negras - Inserção

  • 09/05/2017 - Aula 18 - Árvores Rubro-Negras - Remoção

  • 12/05/2017 - Aula 19 - Tabelas de Espalhamento

  • 16/05/2017 - Aula 20 - Tabelas de Espalhamento, Teste 3

  • 19/05/2017 - Aula 21 - Grafos - Parte 1

  • 23/05/2017 - Aula 22 - Grafos - Parte 2

  • 26/05/2017 - Aula 23 - Grafos - Parte 3

    • Algoritmo de Prim - Árvores Geradoras de Custo Mínimo

    • Ordenação Topológica

      • A ordenação topológica que vimos é baseada em uma variação recursiva da busca em profundidade vista na Aula 21.

      • Veja as seções 22.3 (busca em profundidade) e 22.4 (ordenação topológica) do CLRS.

  • 02/06/2017 - Aula 24 - Árvores B - Definição, Inserção

  • 06/06/2017 - Aula 25 - Árvores B - Remoção

  • 09/06/2017 - Aula 26 - Bloom Filters, Teste 4

  • 13/06/2017 - Aula 27 - Skip Lists

  • 16/06/2017 - Não haverá aula - Corpus Christi

  • 20/06/2017 - Aula 28 - Revisão

  • 23/06/2017 - Aula 29 - Entrega da Lista Coringa, Prova 2

Recursos Online

Programa da Disciplina

  • Estruturas ligadas: nó, apontador, variável apontadora, alocação dinâmica de memória

  • Listas ligadas simples: operações básicas

  • Comparação de listas ligadas com vetores

  • Algoritmos gerais para listas simples: enumeração, inversão, cópia, concatenação

  • Pilhas, filas, e aplicações (eliminação de recursão)

  • Intercalação (merge) de listas e mergesort; análise informal

  • Variações: listas circulares, duplamente ligadas, com cabeça.

  • Algoritmos de ordenação

  • Árvores binárias: representação e percurso (recursivo)

  • Aplicação: árvores de busca (com inserção e remoção)

  • Árvores binárias de busca balanceadas

  • Fila de prioridade (heap) implementação com vetor e heapsort

  • Árvores gerais: definição, representação por listas, percursos

  • Listas generalizadas e uso para representar estruturas ligadas em geral

  • Árvores B e generalizações

  • Hashing: conceito, implementação, técnicas em arquivos

  • Grafos: conceito, representação por matrizes e listas ligadas

  • Percurso de grafos em largura e profundidade

  • Implementação de estruturas de dados em disco

Critério de Avaliação

  • Serão aplicadas 2 provas teóricas P1 e P2. A média das provas teóricas será calculada da seguinte forma:

index__1.png

  • Serão aplicadas 4 mini-provas de curta duração (~30 min.) sempre no final das aulas. Cada mini-prova i (Minii) valerá de 0 a 1. A média das mini-provas MMiniP será dada por:

index__2.png

  • Caso alguém tenha perdido alguma das mini-provas (e apenas neste caso) haverá a oportunidade de fazer uma mini-prova substitutiva. Ela ocorrerá no final do semestre e a data será definida oportunamente. Contudo, caso o aluno tenha perdido mais de uma mini-prova, apenas a nota de uma das mini-provas perdidas será substituida. Portanto, atenção às faltas!

  • Durante o semestre serão dados 4 laboratórios. Os laboratórios 1 e 2 terão peso 2 e os demais peso 3. A média das mini-provas será avaliada em conjunto com as notas dos laboratórios e terá peso 3. A média ML dos laboratórios e mini-provas será dada por:

index__3.png

  • A média M, antes do exame, será calculada da seguinte maneira:

index__4.png

Note a importância de obter bom desempenho tanto nas provas quanto nos laboratórios.

  • Caso o aluno tenha média 2,5 ≤ M < 5,0, ele poderá fazer um exame final (seja E a nota do exame).

  • A nota final, F, será calculada como:

index__5.png

  • O aluno estará aprovado caso sua nota final F seja maior ou igual a 5,0 e estará reprovado caso contrário.

Bibliografia

  • [Feofiloff] P. Feofiloff. Algoritmos em Linguagem C. Campus-Elsevier, 2009.

  • [Sedgewick] R. Sedgewick. Algorithms in C. Addison-Wesley, 1990.

  • [TLA] A. M. Tenenbaum, Y. Langsam, and M. J. Augenstein. Data Structures using C. Prentice-Hall, 1990.

  • [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and Clifford Stein. Introduction to Algorithms, second edition. MIT Press, 2009.

  • [Mamber] U. Mamber, Introduction to Algorithms - A Creative Aproach, Addison-Wesley Publishing Company, 1989.

  • [Knuth] D. E. Knuth. The Art of Computer Programming, volume I: Fundamental Algorithms. Addison-Wesley, 1978.

  • [KR] B. W. Kernighan, D. M. Ritchie. The C Programming Language (2a. edição), Prentice-Hall, 1988