Programação das aulas

Sujeito a mudanças...

Março

• 3 de março (Aula 1):
  • Informações gerais [ps.gz] [pdf]
  • Introdução
  • Listas lineares

• 6 de março (Aula 2):
  • Entrega do EP1 (Aeroporto)
  • Listas ligadas
  • Filas
  • Lista 1
  Transparências [pdf][ps.gz]
  Exercício: Escreva uma implementação de fila, com as 5 operações vistas em aula, usando uma lista ligada. Seria vantajoso usar uma lista duplamente ligada? Seria vantajoso usar cabeça de lista? Seria vantajoso usar uma lista circular? Pense e decida qual lhe parece a melhor variante de lista ligada para implementar estas operações.
  Extra: Veja aqui uma solução para o problema do ratinho, com uma fila implementada em um vetor, com realocação a cada vez que há overflow.
  Leitura recomendada: Capítulo 10 do CLRL.

• 10 de março (Aula 3):
  • Aplicações de filas: cálculo de distância (sem comprimento; busca em largura) e implementação de round-robin, o RRDtool
  • Filas de prioridade
  • Heaps
  Transparências [pdf][ps.gz]
  Extra: um pouco sobre o RRDtool.

• 13 de março (Aula 4):
  • Pilhas
  • Aplicações: cálculo de expressões aritméticas, notação posfixa, linguagem postscript, administração de memória em tempo de execução, casco convexo (CLRS sec 35.3): o algoritmo de Graham
  • Lista 2
  Transparências [pdf][ps.gz]
  Veja o arquivo desenho.ps com o exemplo visto em aula levemente alterado. Para visualizar um arquivo .ps você pode usar o programa gv do unix/linux (ou ghostview para windows). Para ver o arquivo fonte (e não o desenho produzido) ou alterá-lo, use um editor de arquivos texto qualquer, como por exemplo o que você usa para editar seus programas em C.
  Quer aprender mais sobre postscript? Visite aqui a página do Luc Devroy sobre isso.
  Exercício 1: Escreva um arquivo texto desenho1.gz em postscript com o desenho de uma estrela de 6 pontas, usando a função hill vista em aula e presente no arquivo acima.
  Exercício 2: Escreva um arquivo texto desenho2.gz em postscript com o desenho de uma estrela de 5 pontas.
  Exercício 3: Suponha que inserimos e removemos os elementos 1,2,...,n de uma pilha em alguma ordem onde as inserções vêm na ordem 1,2,...,n (mas eventualmente intercaladas com as remoções). Caracterize as permutações de 1 a n que podem ser obtidas como ordem de saída da pilha. (Ou seja, determine uma condição necessária e suficiente que uma permutação tem que ter para que possa ser obtida como saída.)
  Exemplo: A permutação 2,1,3 pode ser obtida, enquanto que a permutação 3,1,2 não.
  Exercício 4: Resolva o exercício 3 acima com uma fila no lugar da pilha.
  Desafio: No pior caso, quanto espaço (em notação assintótica) da pilha de execução pode consumir a implementação usual do quicksort para ordenar um vetor de tamanho n? Como implementar o quicksort de modo a gastar (assintoticamente) menos que isso?
  Leitura recomendada: seção 4.3 do livro do Sedgewick, Algorithms in C, Parts 1-4.

• 17 de março (Aula 5):
  • Implementação de pilha com lista ligada
  • Mais aplicações de pilhas: backtrack (geração de todas as subseqüências em ordem lexicográfica, coloração de mapas, etc)
  • Manipulação de polinômios
  Transparências [pdf][ps.gz]
  Dificuldades com backtrack? Leia a seção 3.4 do Wirth, pg 120-129, onde ele tenta dar uma receita para se projetar algoritmos de tentativa e erro.

• 20 de março (Aula 6):
  • Manipulação de polinômios esparsos
  • Representação de matrizes esparsas
  Transparências [pdf][ps.gz]

• 24 de março (Aula 7):
  • Manipulação de matrizes esparsas
  • Skip lists
  • Lista 3
  Transparências [pdf][ps.gz]

• 27 de março (Aula 8):
  • Skip lists: análise
  • Entrega do EP2 (Busca em janelas)
  Gostaria de ler um pouco sobre skip graphs? Veja a dissertação de mestrado do Hammurabi, que pode ser acessada na Biblioteca Digital de Teses e Dissertações da USP. (Procure por Hammurabi que vem apenas ele como resultado da busca.) Além disso, aqui você concontra a implementação que ele fez.

• 31 de março:
  • Prova 1
  Matéria da prova: listas ligadas, listas circulares, duplamente ligadas, com ou sem cabeça, listas lineares, filas, pilhas, filas de prioridade, e suas aplicações, polinômios e matrizes esparsas, e skip lists.

Abril

Maio