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

• Livro
  • http://www.elsevier.com.br/site/produtos/Detalhe-produto.aspx?tid=59803&seg=20&isbn=978-85-352-3699-6&origem=AUTOR&tit=Algoritmos%20-%203%20EDI%C3%87%C3%83O
• Curso de PAA do MIT
  • http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
• Curso de PAA da pós-graduação da PUC-Rio
  • http://www-di.inf.puc-rio.br/~milidiu/inf2926/aulas/
• Problemas NP completos
  • Teoria: https://www.youtube.com/watch?v=moPtwq_cVH8
  • Resumo da teoria: https://www.youtube.com/watch?v=YX40hbAHx3s
  • Exemplos de problemas: https://www.youtube.com/watch?v=eHZifpgyH_4