The Assignment

This assignment contains two main parts:

Part $1[40$ marks$]-$ extension of the SSet interface that supports two extra operations

The IndexedSSet interface is an extension of the SSet interface described in the textbook that supports two extra operations

$-$ get $($i$)$: return the value at index $\backslash ($ i $\backslash ),$ in other words, return the value $\backslash ($ x $\backslash )$ in the set that is larger than exactly $\backslash ($ i $\backslash )$ other elements in the set.

$-\backslash (\backslash$quad $\backslash )$ spanLength $\backslash (($x$,$ y$)\backslash )$ : return the number of elements in the set that are between the values $\backslash ($ x $\backslash )$ and $\backslash ($ y $\backslash )$ inclusive $(\backslash ($ x $\backslash )$ is not necessarily smaller than $\backslash ($ y $\backslash )).\backslash ($ x $\backslash )$ and $\backslash ($ y $\backslash )$ are not necessarily in the set.

Currently, there are two identical implementations of the IndexedSSet interface using skiplists included in the assignment: SkippitySlow and SkippityFast. Despite their names, both are slow: each has implementations of get $($ i $)$ and spanLength $(\backslash (\backslash$mathrm$\{$x$\},\backslash$mathrm$\{$y$\}\backslash ))$ that run in $\backslash (\backslash$Omega$($n$)\backslash )$ time, in the worst case.

Modify the SkippityFast implementation so that the get$($i$)$ and spanLength$(\backslash ($ x$,$ y $\backslash ))$ operations each run in $\backslash (\backslash$boldsymbol$\{$O$\}(\backslash$log $\backslash$boldsymbol$\{$n$\})\backslash )$ expected time and none of the other operations $($add $\backslash (($x$)\backslash ),$ remove $\backslash (($x$)\backslash ),$ find $\backslash (($x$)\backslash ),$ etc.$)$ have their running$-$time increased by more than a small constant factor. Note that to achieve this, you will have to modify the implementations of add $\backslash (($x$)\backslash )$ and remove $\backslash (($x$)\backslash )$ operations. Other