7. Randomization: Skip Lists 

0:26 today's lecture is about randomized data structure called skip list 0:36 because it is randomized, we have to do probabilistic analysis 4:01 context of skip list 4:51 you can think of the skip list as beginning with a simple linked list 5:09 first think of it as unsorted 6:00 go ahead to think of it as sorted double-linked list 6:20 you have a pointer to the front of the list 6:25 and it is double linked list 6:27 Q: what is the complexity of search in a sorted double linked list 7:30 sorting does not help with respect to the search 8:10 say we have two sorted linked list 9:30 there is not going to be another element on top of each element 10:21 the other linked list is randomized 10:38 the given example is the subway stops - 7th revenue express line in New York city 12:15 basic notion of skip list 12:53 it is really simple 14:15 expression of the search algorithm 16:00

Not only is he great at teaching, he is also super funny while at it lol Some quality teaching right here!

Thanks for the lecture. My university has a problem of having very limited curriculum for Upper division courses, and most of the staff is teaching lower division. So once I graduated with my bachelors degree I discovered OCW and I am just going to do independant self study and hopefully I can get some help from my school taking "special topics in computer science", over and over and hopefully I can gain higher proficiency than what is normally available to the University.

Comparing skip lists to express lines is amazing.

My professor: skip lists hmmm, I am leaving it , do that in your assignment

this guy teaches better than all my prof ; wish i was an MIT student !!!

dishing out knowledge and frisbees!

Chalk board: Every Brilliant teacher's best friend

How i wish, my college professors were half this good with teaching

A Skip List needs a reference to 2 nodes, the previous and the next one. This helps positioning which gives the O(log n). Not gonna go deeper because it's based on Linked List and insert(e) function with a height level added to it.

Insertion in Skip Lists: 36:13

every once in a while the chalk makes a screeching noise and it's the most painful sound in the universe like someone dragging their bare nails on the chalk board.

great lecture; thanks for sharing!

To reach 66, we will move to 72 and then backwards. That was a nice answer.

Great course!

excellent video, thanks

That's great, thank you a lot!

Skip list is kind of like van Emde Boas Tree, right?

Frisebee for wrong answer.. where do you teach? .. lol

12:00 I don't understand why he avoids overshooting here. Since traveling on L1 is faster, going to 72 and then back to 66 should have the minimum amount of nodes, right ?

How bout express to 72nd street then back to 66th street?

Where does that constant (2) comes from 22:33 2 Sorted Linked List -> 2 * Sqrt(n). Can anyone please explain

i said log n i want my frisbee :(

it's good

even i want a free frisbee

7:11 walk of shame

7:17 - It's a[i] (a of i, not AFI) - Meaning, the index place in an a array

Check out Erik's Video, I liked it better though the video quality is bad, ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists/

The other teacher is a lot better.

The Skip list is not doublylinkedList rather it is a SinglyLikedList, every node has a pointer to the next element not to the previous one.

How bout express to 72nd street then back to 66th street?