MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

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)

Switch off the lights

Slides

Related Open Educational Resources

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.

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

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:

1 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

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

sadfas

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

4 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:

Comment:
Name:
Email address:
URL:

make sure you have javascript enabled or clear this field: