Cronograma de MAC122

Fevereiro e março

Abril

• 1 de abril (Aula 9):
  • Implementação da interface fila.h com lista ligada.
  • Implementação da interface fila.h com lista ligada circular com cabeça de lista.
  • Solução do problema do ratinho com as diversas implementações da interface fila.h. [exemplo de labirinto para testar o algoritmo]
  Exercício: Descreva uma interface para uma fila dupla, que é uma fila em que podem haver inserções tanto no início quanto no fim. Remoções continuam sendo permitidas apenas no início da fila. Escreva uma implementação da sua interface usando vetor e outra usando lista ligada. Discuta as vantagens e desvantagens.
• 3 de abril
  • Primeira prova.
  Matéria da prova: tipos abstratos de dados (noções de programa cliente, interface e implementação), listas ligadas e filas.
• 8 de abril (Aula 10):
  • Implementação da interface de fila dupla usando vetor (item a da primeira questão da prova).
  • Notação posfixa.
• 10 de abril (Aula 11):
  • Pilha: interface e implementações.
  • Cálculo de notação posfixa. [solução]
  Exercício: Converta o programa acima para que ele, em vez de simplesmente imprimir a expressão posfixa, monte uma outra string com a expressão posfixa, e depois imprima essa.
• 15 de abril (Aula 12):
  • Cálculo de expressões. [solução]
  Exercício: Dada uma seqüência de (,),[,],{ e }, decidir se ela é ou não bem-formada. Informalmente, uma seqüência de (,),[,],{ e } é bem-formada se os pares estão "casando" corretamente. Assim, por exemplo,
  1. ([]()) é bem formada.
  2. [(){(()())()}] é bem-formada.
  3. []({}([])) é bem-formada.
  4. [) não é bem-formada.
  5. ()()) não é bem-formada.
  6. ){}( não é bem-formada.
  7. []}{ não é bem-formada.
  8. {[]()}(){}) não é bem-formada.
  9. [{]} não é bem-formada.
  Escreva um programa que lê um inteiro n>0 e uma seqüência com n (,),[,],{ e } e imprime se a seqüência é ou não bem-formada.
  Leitura recomendada: notas de aula sobre pilha.
  
• 17 de abril (Aula 13):
  • Recursão: fatorial, combinação, potência, números de Fibonacci, função de Ackermann e torres de Hanói.
• 24 de abril (Aula 14):
  • Recursão: funções recursivas envolvendo vetores e listas ligadas.
  • busca binária [notas de aula]
  Leitura recomendada: notas de aula sobre recursão.
• 29 de abril (Aula 15):
  • Algoritmos de ordenação e recursão.
  • Exercício bônus para a P1.