Sumários
The min-cut problem
20 março 2018, 11:00 • Alexandre Francisco
Las Vegas and Monte Carlo algorithms, properties and examples (MR 1.2). The min-cut problem and the Karger-Stein algorithm: its complexity, success probability and the use of boosting to improve the success probability (MR 10.2).
Lab 03
15 março 2018, 11:00 • Luís Manuel Silveira Russo
Project support. PQ and Prim's algorithm implementation.
Structures for Disjoint Set
14 março 2018, 11:00 • Luís Manuel Silveira Russo
Data structures for disjoint set, supporting union and find. Using linked lists and a forest of trees, Cap 21 CLRS.
Lab 03
13 março 2018, 12:30 • Alexandre Francisco
Project support. PQ and Prim's algorithm implementation.
Expected linear time MST algorithm
13 março 2018, 11:00 • Alexandre Francisco
Boruvka's algorithm: analysis and implementation (MR 10.3). Expected linear time MST algorithm: main results and analysis (MR 10.3).