CTCO04 - Projeto e Análise de Algoritmos - 2025s2

Informações:

Docente: Prof. Dr. Pedro H. D. B. Hokama - IMC
Aulas: Terças das 15:45 até as 17:35 no LDC1 e Quintas das 15:45 até 17:35 no LDC1.
Monitoria: Via discord com a Ana Andrade (anaclarans@unifei...) segunda às 13:30 e quarta às 08:15.

Noticias:

27/11 - Disponibilizado enunciado do Trabalho 04.
31/10 - Atualizado notas.
31/10 - Disponibilizado enunciado do Trabalho 03 (atualizado).
23/10 - Divulgado notas da P1.
23/10 - Sala da Prova - B.4.2.11.
02/10 - Disponibilizado enunciado do Trabalho 02.
30/09 - Prova P1 marcada para 23/10.
08/09 - Disponibilizado enunciado do Trabalho 01.
08/09 - Disponibilizado enunciado do Trabalho 00, no runcodes.
29/07 - Site da Disciplina no Ar

Aulas:

27/11 - Limitantes e Algoritmo de Branch-and-Bound. Slides.
25/11 - Heuristicas e Algoritmos de Aproximação para KNAPSACK. Slides.
11/11 - Algoritmos Exatos para o VERTEX-COVER e para o TSP. Slides.
06/11 - Prova que HAM-CYCLE, TSP e SUBSET-SUM são NP-Completos. Slides.
04/11 - Prova que CIRCUIT-SAT, SAT e 3-CNF-SAT são NP-Completos. Slides.
30/10 - Reduções. Prova que CLICK e VERTEX-COVER são NP-Completos. Slides.
28/10 - Classes de Complexidade: P, NP, NP-Difícil e NP-Completo. Slides.
16/10 - Programação Dinâmica: Problema do Alinhamento de Sequência e Problema da Parentização de Multiplicação de Matrizes. Slides.
14/10 - Programação Dinâmica: Problema do Conjunto Independente no Grafo Caminho, Problema da Mochila. Slides.
02/10 - Algoritmos Gulosos: Problema da Compressão de Dados - Código de Huffman. Slides.
30/09 - Algoritmos Gulosos: Problema do Caminho mínimo - Algoritmo de Dijkstra. Problema do Escalonamento Ponderado. Slides.
18/09 - O Problema do Corte Mínimo em Grafos: Algoritmo de Karger. Slides.
16/09 - O Problema da Seleção. Um limitante inferior para o problema da Ordenação por comparação. Slides.
11/09 - Quick-Sort: complexidade. Slides.
09/09 - Quick-Sort: corretude. Revisão de Probabilidade. Slides.
04/09 - O Teorema Mestre. Slides.
02/09 - Divisão e Conquista: Multiplicação de Matrizes e o Teorema Mestre. Slides.
21/08 - Análise Assintótica, notação o pequeno, omega pequeno. Divisão e Conquista Slides.
19/08 - Análise Assintótica, notação O, Omega e Theta. Slides.
14/08 - Merge Sort, Introdução à Análise Assintótica. Slides.
12/08 - Apresentação, Plano e Algoritmo de Karatsuba. Slides.

Critérios de Avaliação:

Tt = nota dos Trabalhos do Bimestre t.
Pt = nota da Prova do Bimestre t.
Nt = min(Tt, Pt).
M = (N1 + N2) / 2.
Se freq < 75% o aluno reprovou-se.
Senão, se M >= 6 o aluno aprovou-se.
Senão, se M < 6 o aluno faz uma sub que substitui a menor entre N1 e N2.

Referências bibliográficas e Material de Apoio:

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. (2012) Algoritmos - Teoria e Pratica, 3ª edição, GEN LTC.
ROUGHGARDEN, T. (2017) Algorithms Illuminated (Parte 1 a 4), Soundlikeyourself Publishing.