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