Cronograma de MAC122

Agosto

Setembro

• 2 de setembro:
  • Primeira prova.
  Matéria da prova: recursão, pilha e suas aplicações, listas ligadas.
  Isso corresponde aos capítulos 2, 3, 4 e 6 do livro do Prof. Paulo.

• 14 de setembro (Aula 10):
  • Ordenar uma lista ligada...
  • Algoritmos básicos de ordenação: inserção e seleção direta
  • Filas: uma breve introdução

• 16 de setembro (Aula 11):
  • Fila: cálculo de distância
  • Implementação com vetor: fila.h e fila.c
  • Veja o cliente que calcula distancia usando esta biblioteca [distancia.c]
  • Lista 2: exercício 1 abaixo, a ser entregue na aula do dia 23 de setembro.
  Leitura recomendada: Capítulo 5 do livro do Prof. Paulo, ou seção Filas das suas notas de aula.
  Exercício 0: Gere o arquivo fila.o a partir dos arquivos fila.h e fila.c acima. Você pode fazer isso usando o comando gcc -c fila.c -o fila.o. Depois, compile o arquivo cliente, o distancia.c, com o seguinte comando: gcc fila.o distancia.c -o distancia.exe. Experimente então executar o distancia.exe.
  Exercício 1: Escreva uma implementação de fila com lista ligada. Ou seja, escreva um outro arquivo fila.c (leia o exercício 0), que implemente a fila usando uma lista ligada. Refaça o exercício 0 com o seu arquivo fila.c no lugar do arquivo fila.c acima. Tudo deve funcionar sem que você precise alterar nem o fila.h nem o distancia.c.

• 21 de setembro (Aula 12):
  • Problema do ratinho [ratinho.c] [fila.h]
  • Busca binária
  Leitura recomendada: Capítulo 7 do livro do Prof. Paulo ou seção Busca binária das suas notas de aula.

• 23 de setembro (Aula 13):
  • Busca binária: outra versão
  • Implementação de fila com lista ligada circular
  • Algoritmos elementares de ordenação: inserção e seleção
  Leitura recomendada: Capítulo 8 do livro do Prof. Paulo ou seção Ordenação: algoritmos elementares das suas notas de aula.

• 28 de setembro (Aula 14):
  • Ordenação: mergesort
  Leitura recomendada: Capítulo 9 do livro do Prof. Paulo ou seção Ordenação: algoritmo Mergesort das suas notas de aula.

• 30 de setembro (Aula 15):
  • Ordenação: quicksort
  • Tarefa 3: faça um estudo experimental simples dos algoritmos inserção, seleção, mergesort e quicksort. Use os códigos dos algoritmos de ordenação disponíveis nas notas de aula do Prof. Paulo. Ajuste cada função para que devolva o número de comparações efetuadas pelo algoritmo para ordenar o vetor dado. No main, para n = 100, 200, 400, 800, 1600, 3200, 6400, 12800, gere 10 permutações aleatórias de 1 a n, ordene cada uma das permutações com os 4 algoritmos, e imprima uma tabela ao final com a média do número de comparações efetuada pelos 4 algoritmos em cada grupo de 10 permutações do mesmo tamanho.
    Depois de analisar a saída do seu programa, acrescente um comentário no final do seu programa com a saída produzida e com suas impressões sobre os resultados. Elabore sobre o que você percebeu do experimento.
    Se algum algoritmo ficar muito lento para valores grandes de n, remova-o do experimento para tais valores, e fale sobre isso nas suas conclusões.
    Entrega da tarefa 3: 14 de outubro.
  Leitura recomendada: Capítulo 11 do livro do Prof. Paulo ou seção Ordenação: algoritmo Quicksort das suas notas de aula.