Cronograma de MAC122 - fevereiro e março

Fevereiro

• 25 de fevereiro (Aula 1):
  • Introdução (parte do cap 1 do Sedgewick)
  • Tipos de dados, tipos abstratos de dados e estruturas de dados.
  • Problema de conexidade.
  • union-find - implementação 1.
• 27 de fevereiro (Aula 2):
  • Problema de conexidade - continuação (restante do cap 1)
  • union-find - implementação 2.
  • union-find - implementação 3.
  • discussão e análise das três implementações.
  • Comentários sobre a implementação 3. [ps.gz][pdf]
  Exercício: Escreva um programa que resolva o problema da conexidade usando a heurística dos tamanhos e compressão de caminhos. (Entrega: na aula de 4/3)
  Exercício: Escreva um programa que implementa uma variante da implementação 3 onde mantemos não o número de elemento em cada árvore, mas a altura de cada árvore, e use essa informação em vez do vetor tam da implementação 3.

• 4 de março (Aula 3):
  • Questionário [Respostas compiladas]
  • Tipos primitivos do C (seções 3.1 e 3.2 do Sedgewick).
  • Definição de tipos novos de dados (definição da interface e implementação).
  • Crivo de Eratosthenes (implementação 1 e implementação 2).
  Leitura recomendada: apontadores e alocação de memória e estruturas (structs).
  Exercício: Escreva um programa que imprima os números primos entre 1 e N usando um algoritmo que decide se um número é primo ou não testando seus potenciais divisores. Compare o tempo de execução deste algoritmo para N suficientemente grande com o tempo de execução das implementações acima. (Traga as suas impressões no dia 11/3. Não precisa entregar nada. Apenas venha pronto para discutir o que você observou.)
  
• 6 de março (Aula 4):
  • Listas ligadas (seção 3.3 do Sedgewick).
  • Problema de Joseph [solução]
• 11 de março (Aula 5):
  • Diferença entre vetores e listas ligadas.
  • Implementação de listas ligadas com vetores.
  • Funções elementares de manipulação de listas ligadas: imprime, conta e remove. [lista sem cabeça] [lista com cabeça] Qual você gosta mais?
  Exercício: Escreva uma função que verifica se a lista armazenada em uma lista ligada apontada por ini está ordenada em ordem não-decrescente.
  Exercício: Escreva uma função que recebe apontadores para duas células distintas de uma lista ligada e troca as duas de posição na lista ligada. (Para isso, talvez o mais fácil seja escrever uma função que remove uma célula da lista, devolvendo um apontador para ela, e uma que, dado um apontador p para uma célula e um apontador q para uma célula de uma lista ligada, insere p após q na lista ligada.
  
• 13 de março (Aula 6):
  • Lista livre.
  • Interface para listas ligadas.
  • Inversão de uma lista ligada.
  • EP1 - Manipulador de Polinômios Esparsos.
  Leitura recomendada: listas ligadas.
  Exercício: Escreva uma função ordena(apont ini) que recebe uma lista ligada com cabeça de lista e rearranja a lista, devolvendo-a com seus elementos em ordem não-decrescente do valor da chave.
• 18 de março (Aula 7):
  • Listas duplamente ligadas.
  • Filas: problema do ratinho [solução].
  Leitura recomendada: filas.
  
• 20 de março (Aula 8):
  • Interface para filas.
  • Implementação com vetor.
• 25 e 27 de março:
  • Semana santa.