Location: Academic Organisations » OpenCourseWare Consortium » MIT OpenCourseWare » MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

Lecture 12: Skip Lists

author:Erik Demaine, Center for Future Civic Media
published: Feb. 10, 2009,   recorded: October 2005,   views: 527
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 Introduction to Algorithms - Lecture 12
0:16 Skip lists
7:24 One linked list
10:28 Two linked lists
14:17 Two linked lists as a subway
16:59 Searching in two linked lists
17:27 Searching in two linked lists - Example
17:44 Searching in two linked lists
21:03 Design of two linked lists
21:58 Analysis of two linked lists (1)
24:05 Analysis of two linked lists (2)
27:47 More linked lists
32:03 lg(n) linked list
36:23 Searching in lg(n) linked lists
38:22 Skip lists
39:29 Insert(x) (1)
42:03 Insert(x) (2)
48:10 Example of skip list
53:24 Skip list (1)
53:39 Skip list (2)
56:23 With-high-probability theorem (1)
57:39 With-high-probability theorem (2)
60:06 With-high-probability theorem (3)
60:26 Boole's inequality / union bound
67:40 Analysis Warmup (1)
71:44 Analysis Warmup (2)
72:37 Proof of theorem (1)
75:24 Proof of theorem (2)
78:41 Coin flipping analysis (1)
80:48 Coin flipping analysis (2)
82:26 Coin flipping analysis (3)
84:50 Coin flipping analysis (4)

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.

Description

"Good morning. Today we're going to talk about it a balanced search structure, so a data structure that maintains a dynamic set subject to insertion, deletion, and search called skip lists. So, I'll call this a dynamic search structure because it's a data structure. It supports search, and it's dynamic, meaning insert and delete. So, what other dynamic search structures do we know, just for sake of comparison, and to wake everyone up? Shut them out, efficient, I should say, also good, logarithmic time per operation. So, this is a really easy question to get us off the ground..."

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec12_01.pdf (300.4 KB)

Launch Windows Media PlayerLaunch in a standalone WM Player

WMedia PlayerSwitch to Windows Media Player

View slides View slides

Download Flash video Download mit6046jf05_demaine_lec12_01.flv (Flash video 236.3 MB)

Download mp4 video Download mit6046jf05_demaine_lec12_01.m4v (mp4 video 179.2 MB)

Download Real media video Download mit6046jf05_demaine_lec12_01.rm (Real media video 136.8 MB)

Download Windows Media video Download mit6046jf05_demaine_lec12_01.wmv (Windows Media video 755.6 MB)

Download audio transcript Download mit6046jf05_demaine_lec12_01.mp3 (Audio transcript 19.7 MB)

Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

Link this page  

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

Write your own review or comment:

make sure you have javascript enabled or clear this field: