I will cover the following topics tomorrow: -Definition of online algorithms and competitive analysis -Rent or buy problem and computation of competitive ratio for it -The secretary problem and explanation of two randomized online algorithms for this problem -Paging and Caching If time permits, the lecture will also contain a brief on the explanation of online algorithms for list update problem. The lecture is based on these following papers: http://www2.informatik.hu-berlin.de/~albers/papers/brics.pdf [www2.informatik.hu-berlin.de] -- For the paging problem http://lucatrevisan.wordpress.com/2011/03/09/cs261-lecture-17-online-algorithms/ [lucatrevisan.wordpress.com] -- Buy-rent problem/ The secretary problem http://www.cs.princeton.edu/courses/archive/spring13/cos521/notes/lecture5.pdf [www.cs.princeton.edu] -- List update problem Also, The following is an interesting lecture video about online algorithms- paging: http://www.youtube.com/watch?v=IyWOjd-oZ4o [www.youtube.com]