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