Lecture 14: Competitive Analysis: Self-organizing

author: Charles E. Leiserson, Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, MIT
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: November 2005,   views: 13660
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)


Related Open Educational Resources

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.


"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..."

See Also:

Download slides icon Download slides: mit6046jf05_leiserson_lec14_01.pdf (282.8 KB)

Download Video - generic video source Download mit6046jf05_leiserson_lec14_01.m4v (Video - generic video source 155.4 MB)

Download Video - generic video source Download mit6046jf05_leiserson_lec14_01.rm (Video - generic video source 119.2 MB)

Download Video Download mit6046jf05_leiserson_lec14_01.flv (Video 212.4 MB)

Download Video Download mit6046jf05_leiserson_lec14_01_320x240_h264.mp4 (Video 221.1 MB)

Download Video Download mit6046jf05_leiserson_lec14_01.wmv (Video 642.9 MB)

Download audio transcript Download mit6046jf05_leiserson_lec14_01.mp3 (Audio lecture 17.2 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Mike Anderton, April 11, 2013 at 10:29 a.m.:

There is a minor error in slide MTF is O(1)-competitive(2).
ci* = OPT's cost

Regards and Best Wishes
Mike A

Comment2 Choor Choor, April 16, 2019 at 7:33 p.m.:


Comment3 Himanshu mishra, May 17, 2019 at 11:23 a.m.:

It is really easy to use remote desktop connection in windows 10 pc if you were new here then just from here http://remotedesktopwindows10.com get the easiest way to use remote desktop icons in windows 10 pc in few steps.

Comment4 ALM, January 15, 2020 at 8:02 a.m.:

Not really, and that's my whole point. We https://www.jacketsinn.com/ do subtlety. You're creating nuance in your own head and trying to apply it to the way we think.

Write your own review or comment:

make sure you have javascript enabled or clear this field: