Introduction:
Randomization is an important concept, and hence randomization algorithms are
used in a variety of fields, such as number theory, computational geometry, graph
theory, and distributed computing.
The inputs for a randomized algorithm are similar to those of deterministic
algorithms, along with a sequence of random bits that can be used by the algorithm
for making random choices.
In other words, a randomized algorithm is one whose behavior depends on the
inputs, similar to a deterministic algorithm, and the random choices are made as part
of its logic.
As a result, the algorithm gives different outputs even for the same input.
In other words, the algorithm exhibits randomness; hence its run-time is often
explained in terms of a random variable.
Advantages:
Randomized algorithms are known for their simplicity.
Any deterministic algorithm can easily be converted to a randomized algorithm.
These algorithms are very simple to understand and implement.
Randomized algorithms are very efficient.
They utilize little execution time and space compared to any deterministic
algorithms.
Randomized algorithms exhibit superior asymptotic bounds compared to
deterministic algorithms.
In other words, the algorithm complexity of randomized algorithms is better than
that of most deterministic algorithms.
Reliability is an important issue in many critical applications, as not all randomized
algorithms always give correct answers.
In addition, many randomized algorithms may not terminate.
Hence, reliability is an important concern that needs to be dealt with.
The quality of randomized algorithms is dependent on the quality of the random
number generator used as part of the algorithm.
Unlike other design paradigms, a randomized algorithm does not use a single design
principle.
Instead, one should view randomized algorithms as those designed using a set of
principles.
Instead, one should view randomized algorithms as those designed using a set of
principles.
Skip list in Data structure
What is a skip list?
A skip list is a probabilistic data structure. The skip list is used to store a sorted list of
elements or data with a linked list. It allows the process of the elements or data to view
efficiently. In one single step, it skips several elements of the entire list, which is why it is
known as a skip list.
The skip list is an extended version of the linked list. It allows the user to search, remove,
and insert the element very quickly. It consists of a base list that includes a set of elements
which maintains the link hierarchy of the subsequent elements.
Skip list structure
It is built in two layers: The lowest layer and Top layer.
The lowest layer of the skip list is a common sorted linked list, and the top layers of the
skip list are like an "express line" where the elements are skipped.
Complexity table of the Skip list
S. Complexity Average Worst
No case case
1. Access O(logn) O(n)
complexity
2. Search O(logn) O(n)
complexity
3. Delete complexity O(logn) O(n)
4. Insert complexity O(logn) O(n)
5. Space complexity - O(nlogn)
Working of the Skip list
Let's take an example to understand the working of the skip list. In this example, we have 14 nodes,
such that these nodes are divided into two layers, as shown in the diagram.
The lower layer is a common line that links all nodes, and the top layer is an express line that links
only the main nodes, as you can see in the diagram.
Suppose you want to find 47 in this example. You will start the search from the first node of the
express line and continue running on the express line until you find a node that is equal a 47 or
more than 47.
You can see in the example that 47 does not exist in the express line, so you search for a node of
less than 47, which is 40. Now, you go to the normal line with the help of 40, and search the 47,
as shown in the diagram.
Skip List Basic Operations
There are the following types of operations in the skip list.
o Insertion operation: It is used to add a new node to a particular location in a specific
situation.
o Deletion operation: It is used to delete a node in a specific situation.
o Search Operation: The search operation is used to search a particular node in a skip list.
Algorithm of the insertion operation
Insertion (L, Key)
local update [0...Max_Level + 1]
a = L → header
for i = L → level down to 0 do.
while a → forward[i] → key forward[i]
update[i] = a
a = a → forward[0]
lvl = random_Level()
if lvl > L → level then
for i = L → level + 1 to lvl do
update[i] = L → header
L → level = lvl
a = makeNode(lvl, Key, value)
for i = 0 to level do
a → forward[i] = update[i] → forward[i]
update[i] → forward[i] = a
Algorithm of searching operation
Searching (L, SKey)
a = L → header
loop invariant: a → key level down to 0 do.
while a → forward[i] → key forward[i]
a = a → forward[0]
if a → key = SKey then return a → value
else return failure
Example 1: Create a skip list, we want to insert these following keys in the empty skip list.
1. 6 with level 1.
2. 29 with level 1.
3. 22 with level 4.
4. 9 with level 3.
5. 17 with level 1.
6. 4 with level 2.
Ans:
Step 1: Insert 6 with level 1
Step 2: Insert 29 with level 1
Step 3: Insert 22 with level 4
Step 4: Insert 9 with level 3
Step 5: Insert 17 with level 1
Step 6: Insert 4 with level 2
Example 2: Consider this example where we want to search for key 17.
Ans:
Advantages of the Skip list
1. If you want to insert a new node in the skip list, then it will insert the node very fast because
there are no rotations in the skip list.
2. The skip list is simple to implement as compared to the hash table and the binary search
tree.
3. It is very simple to find a node in the list because it stores the nodes in sorted form.
4. The skip list algorithm can be modified very easily in a more specific structure, such as
indexable skip lists, trees, or priority queues.
5. The skip list is a robust and reliable list.
Disadvantages of the Skip list
1. It requires more memory than the balanced tree.
2. Reverse searching is not allowed.
3. The skip list searches the node much slower than the linked list.
Applications of the Skip list
1. It is used in distributed applications, and it represents the pointers and system in the
distributed applications.
2. It is used to implement a dynamic elastic concurrent queue with low lock contention.
3. It is also used with the QMap template class.
4. The indexing of the skip list is used in running median problems.
5. The skip list is used for the delta-encoding posting in the Lucene search.
Probabilistic Skip Lists:
Structure: In probabilistic skip lists, the decision to include an element in a higher level is
probabilistic. Each element is assigned a level randomly, and the probability of an element
being at level i is often determined by a geometric distribution.
Balancing: The random assignment of levels helps achieve average-case logarithmic time
complexity for search, insert, and delete operations.
Expected Height: On average, the expected height of a probabilistic skip list with n
elements is O(log n).
Deterministic Skip Lists:
Structure: In deterministic skip lists, the decision to include an element in a higher level is
determined by a deterministic rule. Typically, the structure uses a fixed probability
distribution or deterministic criteria to decide the level of each element.
Balancing: Deterministic skip lists are designed to achieve worst-case time complexity
guarantees for search, insert, and delete operations. This is in contrast to probabilistic skip
lists, where performance is analyzed on average.
Deterministic Height: The height of a deterministic skip list is typically controlled to ensure
worst-case logarithmic time complexity for operations.
Probabilistic Analysis:
Probabilistic skip lists are often analyzed using expected values and probabilities. The
analysis involves computing the expected height of the skip list and then determining the
expected time complexity of operations based on this height. This analysis provides an
average-case performance guarantee.
Deterministic Analysis:
Deterministic skip lists are typically analyzed based on worst-case scenarios. The analysis
involves proving that, regardless of the input or the order of operations, the time complexity
of search, insert, and delete operations is logarithmic in the worst case.
