# 4.5: Discussion and Exercises

- Page ID
- 8454

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

Skiplists were introduced by Pugh [62] who also presented a number of applications and extensions of skiplists [61]. Since then they have been studied extensively. Several researchers have done very precise analyses of the expected length and variance of the length of the search path for the \(\mathtt{i}\)th element in a skiplist [45,44,58]. Deterministic versions [53], biased versions [8,26], and self-adjusting versions [12] of skiplists have all been developed. Skiplist implementations have been written for various languages and frameworks and have been used in open-source database systems [71,63]. A variant of skiplists is used in the HP-UX operating system kernel's process management structures [42]. Skiplists are even part of the Java 1.6 API [55].

Exercise \(\PageIndex{1}\)

Illustrate the search paths for 2.5 and 5.5 on the skiplist in Figure 4.1.1.

Exercise \(\PageIndex{2}\)

Illustrate the addition of the values 0.5 (with a height of 1) and then 3.5 (with a height of 2) to the skiplist in Figure 4.1.1.

Exercise \(\PageIndex{3}\)

Illustrate the removal of the values 1 and then 3 from the skiplist in Figure 4.1.1.

Exercise \(\PageIndex{4}\)

Illustrate the execution of \(\mathtt{remove(2)}\) on the `SkiplistList` in Figure 4.3.1.

Exercise \(\PageIndex{5}\)

Illustrate the execution of \(\mathtt{add(3,x)}\) on the `SkiplistList` in Figure 4.3.1. Assume that \(\mathtt{pickHeight()}\) selects a height of 4 for the newly created node.

Show that, during an \(\mathtt{add(x)}\) or a \(\mathtt{remove(x)}\) operation, the expected number of pointers in a `SkiplistSet` that get changed is constant.

Suppose that, instead of promoting an element from \(L_{i-1}\) into \(L_i\) based on a coin toss, we promote it with some probability \(p\), \(0 < p < 1\).

- Show that, with this modification, the expected length of a search path is at most \((1/p)\log_{1/p} \mathtt{n} + O(1)\).
- What is the value of \(p\) that minimizes the preceding expression?
- What is the expected height of the skiplist?
- What is the expected number of nodes in the skiplist?

The \(\mathtt{find(x)}\) method in a `SkiplistSet` sometimes performs redundant comparisons; these occur when \(\mathtt{x}\) is compared to the same value more than once. They can occur when, for some node, \(\mathtt{u}\), \(\texttt{u.next[r]} = \texttt{u.next[r-1]}\). Show how these redundant comparisons happen and modify \(\mathtt{find(x)}\) so that they are avoided. Analyze the expected number of comparisons done by your modified \(\mathtt{find(x)}\) method.

Exercise \(\PageIndex{9}\)

Design and implement a version of a skiplist that implements the `SSet` interface, but also allows fast access to elements by rank. That is, it also supports the function \(\mathtt{get(i)}\), which returns the element whose rank is \(\mathtt{i}\) in \(O(\log \mathtt{n})\) expected time. (The rank of an element \(\mathtt{x}\) in an `SSet` is the number of elements in the `SSet` that are less than \(\mathtt{x}\).)

Exercise \(\PageIndex{10}\)

A finger in a skiplist is an array that stores the sequence of nodes on a search path at which the search path goes down. (The variable \(\mathtt{stack}\) in the \(\mathtt{add(x)}\) code in Section 4.2 is a finger; the shaded nodes in Figure 4.2.1 show the contents of the finger.) One can think of a finger as pointing out the path to a node in the lowest list, \(L_0\).

A finger search implements the \(\mathtt{find(x)}\) operation using a finger, by walking up the list using the finger until reaching a node \(\mathtt{u}\) such that \(\texttt{u.x} < \mathtt{x}\) and \(\texttt{u.next}=\mathtt{null}\) or \(\texttt{u.next.x} > \mathtt{x}\) and then performing a normal search for \(\mathtt{x}\) starting from \(\mathtt{u}\). It is possible to prove that the expected number of steps required for a finger search is \(O(1+\log r)\), where \(r\) is the number values in \(L_0\) between \(\mathtt{x}\) and the value pointed to by the finger.

Implement a subclass of `Skiplist` called `SkiplistWithFinger` that implements \(\mathtt{find(x)}\) operations using an internal finger. This subclass stores a finger, which is then used so that every \(\mathtt{find(x)}\) operation is implemented as a finger search. During each \(\mathtt{find(x)}\) operation the finger is updated so that each \(\mathtt{find(x)}\) operation uses, as a starting point, a finger that points to the result of the previous \(\mathtt{find(x)}\) operation.

Write a method, \(\mathtt{truncate(i)}\), that truncates a `SkiplistList` at position \(\mathtt{i}\). After the execution of this method, the size of the list is \(\mathtt{i}\) and it contains only the elements at indices \(0,\ldots,\mathtt{i}-1\). The return value is another `SkiplistList` that contains the elements at indices \(\mathtt{i},\ldots,\mathtt{n}-1\). This method should run in \(O(\log \mathtt{n})\) time.

Exercise \(\PageIndex{12}\)

Write a `SkiplistList` method, \(\mathtt{absorb(l2)}\), that takes as an argument a `SkiplistList`, \(\mathtt{l2}\), empties it and appends its contents, in order, to the receiver. For example, if \(\mathtt{l1}\) contains \(a,b,c\) and \(\mathtt{l2}\) contains \(d,e,f\), then after calling \(\texttt{l1.absorb(l2)}\), \(\mathtt{l1}\) will contain \(a,b,c,d,e,f\) and \(\mathtt{l2}\) will be empty. This method should run in \(O(\log \mathtt{n})\) time.

Exercise \(\PageIndex{13}\)

Using the ideas from the space-efficient list, `SEList`, design and implement a space-efficient `SSet`, `SESSet`. To do this, store the data, in order, in an `SEList`, and store the blocks of this `SEList` in an `SSet`. If the original `SSet` implementation uses \(O(\mathtt{n})\) space to store \(\mathtt{n}\) elements, then the `SESSet` will use enough space for \(\mathtt{n}\) elements plus \(O(\mathtt{n}/\mathtt{b}+\mathtt{b})\) wasted space.

Exercise \(\PageIndex{14}\)

Using an `SSet` as your underlying structure, design and implement an application that reads a (large) text file and allows you to search, interactively, for any substring contained in the text. As the user types their query, a matching part of the text (if any) should appear as a result.

Hint 1: Every substring is a prefix of some suffix, so it suffices to store all suffixes of the text file.

Hint 2: Any suffix can be represented compactly as a single integer indicating where the suffix begins in the text.

Test your application on some large texts, such as some of the books available at Project Gutenberg [1]. If done correctly, your applications will be very responsive; there should be no noticeable lag between typing keystrokes and seeing the results.

Exercise \(\PageIndex{15}\)

(This exercise should be done after reading about binary search trees, in Section 6.2.) Compare skiplists with binary search trees in the following ways:

- Explain how removing some edges of a skiplist leads to a structure that looks like a binary tree and is similar to a binary search tree.
- Skiplists and binary search trees each use about the same number of pointers (2 per node). Skiplists make better use of those pointers, though. Explain why.