Sumários
T10
7 Maio 2024, 16:30 • João Pedro Guerreiro Neto
Complexity Theory and Approximation Algorithms. Classical examples of approximation algorithms: bin packing, job scheduling, subset sum. Polynomial time approximation scheme solutions. The Euclidean version of the Traveling Salesman Problem.
Student presentations for project 1.
TP9
30 Abril 2024, 18:30 • João Pedro Guerreiro Neto
Exercises about sampling. Exercises about complexity reductions.
T9
30 Abril 2024, 16:30 • João Pedro Guerreiro Neto
Randomized Algorithms: Reservoir Sampling, Sampling by Acceptance-Rejection, and Metropolis-Hasting algorithm.
Complexity Theory, languages and complexity classes, the NP class, reductions, NP-hard and NP-complete problems, a complexity class hierarchy.