Projeto e Análise de Algoritmos

Grupo de e-mail

Inscreva-se: https://groups.google.com/forum/#!forum/paa-ufal.

Nos comunicaremos por esse canal.

Github

https://github.com/r0drigopaes/paa

Google Classroom

  • 2017.2: código: qhtc92d

Avaliação

Serão 2 notas: AB1 e AB2.

Cada AB será composta por: 0.35 * prova teórica + 0.35 * prova prática + 0.15 * exercícios do huxley + 0.15 exercícios no google classroom

Planejamento das aulas

2018.2: https://docs.google.com/spreadsheets/d/1N12ZgEA3KpT1pjV2k19BLEN_TowQ-w7xpj5sjyjTwlI/edit?usp=sharing

Slides

AB1

  1. Introdução.
  2. Eficiência
  3. Dividir e conquistar
  4. Quicksort
  5. Segment tree
  6. Comparação como modelo computacional
  7. Counting Sort
  8. Exercícios de dividir e conquistar
  9. Recorrências
  10. Teorema Mestre
  11. Grafos parte 1
    1. BFS e DFS
    2. Implementação em C++ com listas de adjacências
    3. Flood fill
  12. Método Guloso
  13. Dijkstra
  14. Minimum Spanning Tree

AB2

  1. Programação Dinâmica (vídeo-aulas no youtube)
    1. Exercícios:
      1. Huxley 874 (corte de hastes)
      2. Uva 10066 (LCS)
      3. Uva 531 (LCS)
  2. Grafos parte 2
    1. Ordenação topológica
      1. Vídeo Aulas
        1. Parte 1: https://youtu.be/8JIR4ITnD_Y
        2. Parte 2: https://youtu.be/hI3TUGexJQo
      2. Slides
    2. Pontos de articulação e pontes
    3. Single pair shortest path - Bellman Ford (arestas negativas)
    4. All pair shortest path - Floyd-Warshall
    5. Fluxo Máximo (Ford-Fulkerson)
  3. Problemas NP-Completos e Reduções
  4. CIRCUIT-SAT e outros
  5. Algoritmo de aproximação para o TSP

Referências