Please answer all parts and give reasoning. Your help is greatly appreciated.
#5. Skip Lists (7 points) Here is a skip list, including instance variables s (the starting position), h (the height: we assume that h starts counting from 0), and n (the number of keys currently stored in the skip list). For simplicity, the graphic shows only horizontal lines, but keep in mind that these are doubly linked lists in both the horizontal and vertical directions. You may also use this simplified drawing in your responses h-3, n-4 +inf S2-intf S1-intf SO -intf 15 15 23 -int 10 15 23 36 +inf (a) (1 pt) Trace the path that SkipSearch(23) takes, by circling every node that p is assigned to as the SkipSearch algorithm executes, starting with s. (You may want to print out the diagram, trace it with a dark pen, and scan or photograph it to include in your document.) In the remaining questions, you will show what the skip list shown above looks like after the cumulative operations indicated below, using the pseudocode for Skiplnsert and SkipSearch in the lecture notes, and your understanding of how SkipDelete works from the class activity Since this is a random algorithm and we want everyone to have the same answer to facilitate grading, we give you sequences of random numbers in [0,1] that you should use in tracing the algorithm where the insertion code says while random (0,1) 1/2 do... (Not all of the numbers will be used, as we are testing your understanding of when and how the random numbers are used) The operations are cumulative: each step builds on the result of the previous one. Redraw the entire data structure after each operation, and also update instance variables s, h and n as needed #5. Skip Lists (7 points) Here is a skip list, including instance variables s (the starting position), h (the height: we assume that h starts counting from 0), and n (the number of keys currently stored in the skip list). For simplicity, the graphic shows only horizontal lines, but keep in mind that these are doubly linked lists in both the horizontal and vertical directions. You may also use this simplified drawing in your responses h-3, n-4 +inf S2-intf S1-intf SO -intf 15 15 23 -int 10 15 23 36 +inf (a) (1 pt) Trace the path that SkipSearch(23) takes, by circling every node that p is assigned to as the SkipSearch algorithm executes, starting with s. (You may want to print out the diagram, trace it with a dark pen, and scan or photograph it to include in your document.) In the remaining questions, you will show what the skip list shown above looks like after the cumulative operations indicated below, using the pseudocode for Skiplnsert and SkipSearch in the lecture notes, and your understanding of how SkipDelete works from the class activity Since this is a random algorithm and we want everyone to have the same answer to facilitate grading, we give you sequences of random numbers in [0,1] that you should use in tracing the algorithm where the insertion code says while random (0,1) 1/2 do... (Not all of the numbers will be used, as we are testing your understanding of when and how the random numbers are used) The operations are cumulative: each step builds on the result of the previous one. Redraw the entire data structure after each operation, and also update instance variables s, h and n as needed
