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
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.
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.
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.
@@CodeAndLIfe simple way to think is that skip list structure looks like a binary (search) tree. Another way to think about it is that the number of remaining items to search by when going to other lists to search splits by a constant factor. This constant factor is the base of the log and the log is basically like an inverse of an exponent (repeated multiplication) . Each list we jump to divides the remaining number of inputs to search through. That's how I think of it
I think of a skip list as a multi-way tree with randomized balance. The skip list is like a tree with forward/backward pointers (to the next/previous node at the same level) that turn each level of the tree into a doubly linked list. For new insertions, you randomly choose a height for the node.
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 ?
The issue comes down to this: We have a complete and stativ picture of the subway stops for L0 and L1, so we *know* that overshooting and then going one stop back is faster. Your software/algorithm doesn't have this picture. How does a piece of software get that complete picture? The only way it can get it for any given moment in time would be by iterating through the complete list, at all levels. Once you've done that, you've lost all of the performance/optimisation advantages that a skip-list offers over a regular linked-list, in fact it's slightly slower 😂 If computers could have a "bird-eve" view of a data structure, then they could just insert the value at the right place every time in one step. Unfortunately, there is no such magic.
You can bound the cost |L1| + (|L0|/|L1|) = |L1| + n/|L1| by using AM-GM to get 2sqrt(n). For the cases of k lists you can also use AM-GM to minimize the cost.
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/
It has to be a doubly linked list, other wise you would have disconnections between the levels as a node would not be able to be connected to two other nodes; the next one and the one at the level below.
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
God bless you!
Not only is he great at teaching, he is also super funny while at it lol Some quality teaching right here!
My professor: skip lists hmmm, I am leaving it , do that in your assignment
skip lists... hmm.. let us just *skip* this.
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.
What school?
@@efbdvtfbrt7027 winston Salem state
Comparing skip lists to express lines is amazing.
this guy teaches better than all my prof ; wish i was an MIT student !!!
True man❤️❤️❤️❤️❤️❤️
you are virtually one now!
no cap
Insertion in Skip Lists: 36:13
Chalk board: Every Brilliant teacher's best friend
dishing out knowledge and frisbees!
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.
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.
Any idea how can I understand how log n is derived?
@@CodeAndLIfe simple way to think is that skip list structure looks like a binary (search) tree. Another way to think about it is that the number of remaining items to search by when going to other lists to search splits by a constant factor. This constant factor is the base of the log and the log is basically like an inverse of an exponent (repeated multiplication) . Each list we jump to divides the remaining number of inputs to search through.
That's how I think of it
I think of a skip list as a multi-way tree with randomized balance. The skip list is like a tree with forward/backward pointers (to the next/previous node at the same level) that turn each level of the tree into a doubly linked list. For new insertions, you randomly choose a height for the node.
To reach 66, we will move to 72 and then backwards. That was a nice answer.
great lecture; thanks for sharing!
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 ?
"That will be another algorithm and its analysis will be more painful than the painful analysis which he is already doing for the skip list."
The issue comes down to this:
We have a complete and stativ picture of the subway stops for L0 and L1, so we *know* that overshooting and then going one stop back is faster.
Your software/algorithm doesn't have this picture.
How does a piece of software get that complete picture? The only way it can get it for any given moment in time would be by iterating through the complete list, at all levels. Once you've done that, you've lost all of the performance/optimisation advantages that a skip-list offers over a regular linked-list, in fact it's slightly slower 😂
If computers could have a "bird-eve" view of a data structure, then they could just insert the value at the right place every time in one step. Unfortunately, there is no such magic.
Great course!
Where does that constant (2) comes from 22:33
2 Sorted Linked List -> 2 * Sqrt(n).
Can anyone please explain
Search cost is already given as |L1| + (|L0|/|L1|).
|L1| is found to be sqrt(n). So is |L0|/|L1|, making the sum 2 * sqrt(n).
You can bound the cost |L1| + (|L0|/|L1|) = |L1| + n/|L1| by using AM-GM to get 2sqrt(n). For the cases of k lists you can also use AM-GM to minimize the cost.
Skip list is kind of like van Emde Boas Tree, right?
excellent video, thanks
That's great, thank you a lot!
7:17 - It's a[i] (a of i, not AFI) - Meaning, the index place in an a array
You do realize that that's the way he pronounces 'of'?
even i want a free frisbee
7:11 walk of shame
Frisebee for wrong answer.. where do you teach? .. lol
Dude it's MIT, wrong answer is pretty rare there... I think lol
it's good
How bout express to 72nd street then back to 66th street?
Its Fails!
Its an Exception case
Thats what one of the students asked, he said we will not deal with going ahead than back, because it would be harder to analyze.
the answer that you came up with which precondition is u has scan L0 already
i said log n i want my frisbee :(
Same here 😅
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.
It's difficult to update a Skiplist efficiently without backpointers
every node has a pointer to the next element of the same height and the element below it.
every node is a quadnode in skiplist..correct me if im wrong.
It has to be a doubly linked list, other wise you would have disconnections between the levels as a node would not be able to be connected to two other nodes; the next one and the one at the level below.
@@siddheshkandarkar235 what is a quad node?
How bout express to 72nd street then back to 66th street?
Lol wow. That's a modification worth observing.