Sumários

Lecture 12

25 maio 2012, 10:00 Alexandre Francisco

Conclusion of exercises from previous lecture. An exercise on developing online MST algorithm.


Not Taught.

25 maio 2012, 08:30 Alexandre Francisco

No more theoretical classes.


Online algorithms

21 maio 2012, 08:30 Alexandre Francisco

Randomized online paging algorithms. Adversary models: oblivious adversary; adaptive online adversary; adaptive offline adversary; competitiveness coefficients and properties. Paging against an oblivious adversary: lower bound and the Marker algorithm.


Lecture 11

18 maio 2012, 10:00 Alexandre Francisco

Problems 10.17 and 10.18 and exercise 6.1 from the book "Randomized Algorithms".


Online algorithms

18 maio 2012, 08:30 Alexandre Francisco

Introduction, motivation and basic concepts. Online paging problem: definition; offline optimal algorithms; deterministic online algorithms. Competitiveness coefficient. A lower bound on the competitiveness coefficient for deterministic online paging algorithms.