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.
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
TP8
23 Abril 2024, 18:30 • João Pedro Guerreiro Neto
Exercises using Las Vegas and Monte Carlo algorithms.
T8
23 Abril 2024, 16:30 • João Pedro Guerreiro Neto
Randomized Algorithms. Las Vegas and Monte Carlo approaches. Use of Probability Theory. Randomized data structures: Skip Lists and Treaps. Monte Carlo algorithms: polynomial identity, approximate counting (Morris counters).