ANALYSIS OF ALGORITHMS (89-755-01) 

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

Amortized analysis

· Three methods for amortized analysis

Chapter 18, Introductions to algorithms, CLR

Splay trees

· Sleator and Tarjan paper

· MIT course

Online algorithms

List Access Problem

Paging

K-Server

· Yair Bar-Tal's lecture notes

· Susanne Albers's lecture notes

Approximation algorithms

Linear Programs

The Set Cover problem

Exercises

Yonatan Auman's last year rehearsal exercises

Part 1

Part 2

APSP Directions

Other resources on the web:

MIT course

Princeton course