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: 2275
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)

Slides

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

Description

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

Write your own review or comment:

make sure you have javascript enabled or clear this field: