Lecture 14: Competitive Analysis: Self-organizing
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009, recorded: November 2005, views: 2285
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
"And this is going to use some of the techniques we learned last time with respect to amortized analysis. And, what's neat about what we're going to talk about today is it's a way of comparing algorithms that are so-called online algorithms. And we're going to introduce this notion with a problem which is called self organizing lists. OK, and so the set up for this problem is that we have a list, L, of n elements. And, we have an operation. Woops, I've got to spell things right, access of x, which accesses item x in the list..."
Download slides: mit6046jf05_leiserson_lec14_01.pdf (282.8 KB)
Download mit6046jf05_leiserson_lec14_01.m4v (Video - generic video source 155.4 MB)
Download mit6046jf05_leiserson_lec14_01.rm (Video - generic video source 119.2 MB)
Download mit6046jf05_leiserson_lec14_01.flv (Video 212.4 MB)
Download mit6046jf05_leiserson_lec14_01.wmv (Video 642.9 MB)
Download mit6046jf05_leiserson_lec14_01.mp3 (Audio lecture 17.2 MB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !