Cronograma de MAC122 - fevereiro e março

Fevereiro

• 26 de fevereiro (Aula 1):
  • Introdução
  • Questionário
  • Problema de conexidade.
    Considere uma seqüência de pares de inteiros onde cada inteiro representa um objeto e um par p-q indica que "p está ligado a q". Assuma que a relação "estar ligado a" é transitiva, ou seja, se p está ligado a q e q está ligado a r, então p está ligado a r.
    Objetivo: escrever um programa que leia pares de inteiros e imprima um par apenas se este já não for conseqüência dos anteriores, ou seja, um par p-q é impresso apenas se os pares anteriores não implicarem que p está ligado a q. Se p está ligado a q, então o par p-q não é impresso e passa-se ao próximo par.
  • Operações find e union
  • Primeira implementação do union-find: a chamada quick-find. Usa-se um vetor id onde id[i] = id[j] se e somente se i e j estão conectados. [impl 1]
  • Segunda implementação do union-find: a chamada quick-union. [impl 2]
  • Terceira implementação do union-find: quick-union com heurística dos tamanhos. [impl 3]
  Leitura recomendada: Seções 1.2 e 1.3 do Sedgewick.

  Além das implementações, pegue algumas entradas para você testar com os programas acima e sentir a diferença no tempo consumido pelas diferentes implementações de union-find. Sinta a diferença que pode fazer a escolha de uma boa estrutura de dados.
  [entrada0] [entrada1] [entrada2]
  Em qual dessas entradas você sentiu mais a diferença de tempo entre as implementações? Qual implementação parece mais rápida? Quão mais rápida?

• 1 de março (Aula 2):
  • Problema de conexidade - continuação
  • Apontadores e alocação dinâmica
  Exercício: Escreva um programa que resolva o problema da conexidade usando a heurística dos tamanhos e compressão de caminhos.
  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.
  Leitura recomendada: Notas de aulas do Prof. Paulo Feofiloff sobre apontadores e sobre alocação dinâmica de memória.

• 5 de março (Aula 3):
  • Tipos primitivos do C
  • Definição de tipos novos de dados (structs, definição da interface e implementação).
  • EP1 - Manipulador de Polinômios Esparsos.
  Leitura recomendada: Seções 3.1 e 3.2 do Sedgewick e notas de aulas sobre estruturas ou registros.

• 8 de março (Aula 4):
  • Crivo de Eratosthenes [impl 1] [impl 2] [impl 3] (seção 3.2 do Sedgewick)
  • Listas ligadas (seção 3.3 do Sedgewick)
  • Lista ligada versus vetor
  Leitura recomendada: Seções 3.2 e e começo da 3.3 do Sedgewick.

• 12 de março (Aula 5):
  • Problema de Joseph [solução1] [solução2]
  • Funções elementares de manipulação de listas ligadas: imprime, conta, busca, remove um elemento.
    [LL sem cabeça] [LL com cabeça]
    Qual das duas implementações você gosta mais?
  • Lista livre.
  • Lista 1
  Leitura recomendada: Notas de aula sobre listas ligadas.

• 15 de março (Aula 6):
  • Intercalação de duas listas ligadas ordenadas.
    [intercalas e outras funções de manipulação de LL]

• 19 de março (Aula 7):
  • Inversão de uma lista ligada.
  • Verifica se está ordenada. [as duas funções acima]
  • Leitura de arquivos [exemplo].
  • Implementação de listas ligadas com vetores.
  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.

• 22 de março (Aula 8):
  • Leitura de argumentos da linha de comando [exemplo].
  • Filas
  • Implementação em vetor

• 26 de março: - não há aula (semana de provas)

• 29 de março:
  • Primeira prova.
  Matéria da prova: tipos abstratos de dados (noções de programa cliente, interface e implementação), vetores, structs, e listas ligadas.

Maio e demais meses