| Aulas | Assunto |
| 01 | Complexidade de Problemas de Decisão com relação a algoritmos exatos |
| 02 | Problemas Decidíveis e Problemas Indecidíveis |
| 03 | Classes P, NP, co-NP, PSPACE e EXPTIME |
| 04 | Redução Polinomial: SAT, 3-SAT e CLIQUE |
| 05 | Problemas NP-Completos e co-NP-Completos |
| 06 | NP-Completude: Clique e Vertex-Cover |
| 07 | NP-Completude: Caminho hamiltoniano |
| 08 | NP-Completude: Soma de subconjunto |
| 09 | PSPACE-Completude: Q-SAT e o jogo GEOGRAFIA |
| 10 | PSPACE-Completude: POSCNF e o jogo da Formação de Clique |
| 11 | PSPACE-Completude: POSCNF e o jogo de Coloração |
| 12 | PSPACE-Completude: POSDNF e o jogo de Dominação |
| 13 | EXPTIME-Completude: Alt-SAT e o Jogo de Polícia e Ladrão |
| 14 | EXPTIME-Completude: Outros jogos de Perseguição em Grafos |
| 15 | Complexidade de Problemas de Decisão com relação a algoritmos probabilísticos |
| 16 | Classes ZPP, RP, coRP e BPP |
| 17 | Algoritmos probabilísticos: Popular, Igualdade Polinômios, Produto Matrizes, Corte Mínimo e 2SAT |
| 18 | Complexidade de Problemas de Otimização com relação a algoritmos aproximativos |
| 19 | Classes NPO, PO, APX, log-APX, poly-APX, exp-APX, PTAS e FPTAS |
| 20 | Problemas FPTAS: Mochila |
| 21 | Problemas PTAS: Escalonamento Mínimo |
| 22 | Problemas APX: Bin-Packing e Vertex-Cover |
| 23 | Problemas log-APX: Set-Cover e Conjunto Dominante |
| 24 | Redução entre problemas de otimização e exemplos simples |
| 25 | Problemas completos das classes NPO, APX, log-APX e poly-APX |
| 26 | Complexidade de Problemas de Decisão com relação a algoritmos parametrizados |
| 27 | Classes XP, FPT, W[1] e W[2] |
| 28 | Redução entre problemas parametrizados |
| 29 | Problemas W[1]-Completos e W[2]-Completos |
| 30 | W[1]-Completude: Clique |
| 31 | W[2]-Completude: Conjunto Dominante |
| 32 | Avaliação e Entrega dos trabalhos |