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:

1. 31/10 - Atualizado notas.
2. 31/10 - Disponibilizado enunciado do Trabalho 03.
3. 23/10 - Divulgado notas da P1.
4. 23/10 - Sala da Prova - B.4.2.11.
5. 02/10 - Disponibilizado enunciado do Trabalho 02.
6. 30/09 - Prova P1 marcada para 23/10.
7. 08/09 - Disponibilizado enunciado do Trabalho 01.
8. 08/09 - Disponibilizado enunciado do Trabalho 00, no runcodes.
9. 29/07 - Site da Disciplina no Ar

Aulas:

• 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.