Numerical Representations

Prev: Lazy Rebuilding Next: Data-Structural Bootstrapping

Prev: Lazy Rebuilding Next: Data-Structural Bootstrapping

9.2 Binary Numbers

9.2.1 Binary Random-Access Lists

Exercise 9.1

Write a function drop of type int * a RList -> a RList that deletes the first k elements of a binary random-access list. Your function should run in $O(\log n)$ time.

Exercise 9.2

Write a function create of type int * a -> a RList that creates a binary random-access list containing n copies of some value x. This function should also run in $O(\log n)$ time. You may find Exercise 2.5 helpful.

Exercise 9.3

Reimplement BinaryRandomAccessList using a sparse representation such as:

datatype a Tree = LEAF of a | NODE of int * a Tree * a Tree
type a RList = a Tree list

9.2.2 Zeroless Representations

Exercise 9.4

Write decrement and addition functions for zeroless binary numbers. Note that carries during additions can involve either ones or twos.

Exercise 9.5

Implement the remaining functions for the type described in this section.

Exercise 9.6

Show that lookup and update on element i now run in $O(\log i)$ time.

Exercise 9.7

Under certain conditions, red-black trees can be viewed as a numerical representation. Compare and contrast zeroless binary random-access lists with red-black trees in which insertions are restricted to the leftmost position. Focus on the cons and insert functions and on the shape invariants of the structures produced by these functions.

9.2.3 Lazy Representations

Exercise 9.8

Prove that inc and dec both run in $O(1)$ amortized time using a debit invariant that allows one debit per ONE and zero debits per ZERO or TWO.

Exercise 9.9

Implement cons, head, and tail for random-access lists based on zeroless redundant binary numbers, using the type:

datatype a Digit =
    ONE of a Tree
  | TWO of a Tree * a Tree
  | THREE of a Tree * a Tree * a Tree
type a RList = Digit Stream

Show that all three functions run in $O(1)$ amortized time.

Exercise 9.10

As demonstrated by scheduled binomial heaps in Section 7.3, we can apply scheduling to lazy binary numbers to achieve $O(1)$ worst-case bounds. Reimplement cons, head, and tail from the preceding exercise so that each runs in $O(1)$ worst-case time.

You may find it helpful to have two distinct TWO constructors, such as Two and Two', so that you can distinguish between recursive and non-recursive cases of cons and tail.

9.2.4 Segmented Representations

Exercise 9.11

Extend binomial heaps with segmentation so that insert runs in $O(1)$ worst-case time. Use the type:

datatype Tree = NODE of Elem.T * Tree list
datatype Digit = ZERO | ONES of Tree list | TWO of Tree * Tree
type Heap = Digit list

Restore the invariant after a merge by eliminating all TWOs.

Exercise 9.12

The example implementation of binary numbers based on recursive slowdown supports inc in $O(1)$ worst-case time, but might require up to $O(\log n)$ for dec. Reimplement segmented, redundant binary numbers to support both inc and dec in $O(1)$ worst-case time by allowing each digit to be 0, 1, 2, 3, or 4, where 0 and 4 are red, 1 and 3 are yellow, and 2 is green.

Exercise 9.13

Implement cons, head, tail, and lookup for a numerical representation of random-access lists based on the number system of the previous exercise. Your implementation should support cons, head, and tail in $O(1)$ worst-case time, and lookup in $O(\log i)$ worst-case time.

9.3 Skew Binary Numbers

9.3.1 Skew Binary Random-Access Lists

Exercise 9.14

Rewrite the HoodMelvilleQueue structure from Section 8.2.1 to use skew binary random-access lists instead of regular lists. Implement lookup and update functions on these queues.

9.3.2 Skew Binomial Heaps

Exercise 9.15

Prove Lemma 9.2.

Exercise 9.16

Suppose we want a delete function of type Elem.T * Heap -> Heap. Write a functor that takes an implementation H of heaps and produces an implementation of heaps that supports delete as well as all the other usual heap functions. Use the type:

type Heap = H.Heap * H.Heap

One primitive heap represents positive occurrences of elements and the other represents negative occurrences. Maintain the invariant that the minimum element of the positive heap is strictly smaller than the minimum element of the negative heap.

9.4 Trinary and Quaternary Numbers

Exercises

Exercise 9.17

Implement trinomial heaps using the type:

datatype Tree = NODE of Elem.T * (Tree * Tree) list
datatype Digit = ZERO | ONE of Tree | TWO of Tree * Tree
type Heap = Digit list

Exercise 9.18

Implement zeroless quaternary random-access lists using the type:

datatype a Tree = LEAF of a | NODE of a Tree vector
datatype a RList = a Tree vector list

Each vector in a NODE contains four trees, and each vector in a list contains one to four trees.

Exercise 9.19

Adapt the notion of skew binary numbers to arbitrary bases. In skew $k$-ary numbers, the ith digit has weight $\frac{k^{i+1}-1}{k-1}$, and each digit is chosen from $\{0,\dots ,k-1\}$ except that the lowest non-zero digit may be k.

Implement skew trinary random-access lists using the type:

datatype a Tree = LEAF of a | NODE of a * a Tree * a Tree * a Tree
type a RList = (int * a Tree) list

9.5 Chapter Notes