Sumários

TP10

7 Maio 2024, 18:30 • João Pedro Guerreiro Neto

Student presentations for project 1.

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.

TP8

23 Abril 2024, 18:30 • João Pedro Guerreiro Neto

Exercises using Las Vegas and Monte Carlo algorithms.