ANALYSIS OF ALGORITHMS (89-755-01) 

 

October 2011 January 2012, Bar-Ilan University
Lecturer: Liam Roditty

 

All pairs of shortest paths

     Seidel's APSP algorithm for unweighted undirected graphs (paper)

     Zwick's APSP algorithm for weighted directed graphs (paper)

Splay trees

 

Approximation algorithms

Linear Programs

The Set Cover problem

Online Algorithms

 

Exercises

Yonatan Auman's last year rehearsal exercises

Part 1

Part 2

APSP

Directions

 

Resources on the web:

Zwick's course

MIT course

Princeton course