# Exercises

## Hashing

##### Exercise: hash insert [✭✭]

Suppose we have a hash table on integer keys. The table currently has 7
empty buckets, and the hash function is simply `let hash k = k mod 7`

.
Draw the hash table that results from inserting the keys 4, 8, 15, 16,
23, and 42 (with whatever values you like).

□

##### Exercise: relax bucket RI [✭✭]

In lecture, we required that hash table buckets must not contain duplicates. What would happen if we relaxed this RI to allow duplicates? Would the efficiency of any operations (insert, find, or remove) change?

□

##### Exercise: strengthen bucket RI [✭✭]

What would happen if we strengthened the bucket RI to require each bucket to be sorted by the key? Would the efficiency of any operations (insert, find, or remove) change?

□

##### Exercise: hash values [✭✭]

`Hashtbl.hash : 'a -> int`

is a hash function provided by
the standard library. This rather remarkable
function can transform a value of any type into an integer.
Use it to hash several values of different types.
Make sure to try at least `()`

, `false`

, `true`

, `0`

, `1`

, `""`

,
and `[]`

, as well as several "larger" values of each type.
Try hashing lists of integers of increasing length (e.g.,
`[0]`

, `[0;1]`

, `[0;1;2]`

, ...). How long can the list get
before you find a collision?

□

## Hashtbl

OCaml's `Hashtbl`

module offers two kinds of hash tables. The
first (and simpler to use) is for clients who are happy to use
OCaml's built-in hash function. The second is for clients
who want to supply their own hash function; naturally, that is done
with a functor.

For the following exercises, consult the documentation of
`Hashtbl`

.

##### Exercise: hashtbl usage [✭✭]

Create a hash table `tab`

with `Hashtbl.create`

whose initial size is 16.
(You can safely ignore the optional argument to that function
for now.) Add 31 bindings to it with `Hashtbl.add`

.
For example, you could add the numbers 1..31 as keys and
the strings "1".."31" as their values. Use `Hashtbl.find`

to look for keys that are in `tab`

, as well as keys
that are not.

□

##### Exercise: hashtbl bindings [✭✭]

Define a function `bindings : ('a,'b) Hashtbl.t -> ('a*'b) list`

,
such that `bindings h`

returns a list of all bindings in `h`

.
Use your function to see all the bindings in `tab`

. *Hint: fold.*

□

##### Exercise: hashtbl stats [✭]

Use the `Hashtbl.stats`

function to find out the statistics
of `tab`

. How many buckets are in the table? How many buckets
have a single binding in them?

□

##### Exercise: hashtbl load factor [✭✭]

Define a function `load_factor : ('a,'b) Hashtbl.t -> float`

,
such that `load_factor h`

is the load factor of `h`

.
What is the load factor of `tab`

? *Hint: stats.*

□

##### Exercise: hashtbl load factor [✭]

Add one more binding to `tab`

. Do the stats or load factor change?
Now add yet another binding. Now do the stats or load factor change?
*Hint: Hashtbl resizes when the load factor goes strictly
above 2.*

□

## Functorial Hashtbl

##### Exercise: functorial interface [✭✭✭]

Use the functorial interface (i.e., `Hashtbl.Make`

) to
create a hash table whose keys are strings that are
case insensitive. Be careful to obey the specification of
`Hashtbl.HashedType.hash`

:

If two keys are equal according to

`equal`

, then they have identical hash values as computed by`hash`

.

□

##### Exercise: equals and hash [✭✭]

The previous exercise quoted the specification of `Hashtbl.HashedType.hash`

.
Compare that to Java's `Object.hashCode()`

specification.
Why do they both have this similar requirement?

□

##### Exercise: bad hash [✭✭]

Use the functorial interface to create a hash table with a really
bad hash function (e.g., a constant function). Use the `stats`

function to see how bad the bucket distribution becomes.

□

## Challenge problem: Probing

In lecture we briefly mentioned *probing* as an alternative to
*chaining*. Probing can be effectively used in hardware implementations
of hash tables, as well as in databases. With probing, every bucket
contains exactly one binding. In case of a collision, we search forward
through the array, as described below.

**Find.** Suppose we are trying to find a binding in the table. We hash
the binding's key and look in the appropriate bucket. If there is
already a different key in that bucket, we start searching forward
through the array at the next bucket, then the next bucket, and so
forth, wrapping back around to the beginning of the array if necessary.
Eventually we will either

find an empty bucket, in which case the key we're searching for is not bound in the table;

find the key before we reach an empty bucket, in which case we can return the value; or

never find the key or an empty bucket, instead wrapping back around to the original bucket, in which case all buckets are full and the key is not bound in the table. This case actually should never occur, because we won't allow the load factor to get high enough for all buckets to be filled.

**Insert.** Insertion follows the same algorithm as finding a key,
except that whenever we first find an empty bucket, we can insert the
binding there.

**Remove.** Removal is more difficult. Once the key is found,
we can't just make the bucket empty, because that would affect
future searches by causing them to stop early. Instead,
we can introduce a special "deleted" value into that bucket
to indicate that the bucket does not contain a binding but
the searches should not stop at it.

**Resizing.** Since we never want the array to become
completely full, we can keep the load factor near 1/4.
When the load factor exceeds 1/2, we can double the array,
bringing the load factor back to 1/4. When the load factor goes below
1/8, we can half the array, again bringing the load factor
back to 1/4. "Deleted" bindings complicate the definition
of load factor:

When determining whether to double the table size, we calculate the load factor as (# of bindings + # of deleted bindings) / (# of buckets). That is, deleted bindings contribute toward increasing the load factor.

When determining whether the half the table size, we calculate the load factor as (# of bindings) / (# buckets). That is, deleted bindings do not count toward increasing the load factor.

When rehashing the table, deleted bindings are of course not re-inserted into the new table.

##### Exercise: linear probing [✭✭✭✭]

Implement a hash table that uses linear probing.

□

## Trees

##### Exercise: functorized BST [✭✭✭]

Our implementation of BSTs in lecture assumed that it was okay
to compare values using the built-in comparison operators `<`

, `=`

,
and `>`

. But what if the client of the `Set`

abstraction wanted to
use their own comparison operators? (e.g., to ignore case in strings,
or to have sets of records where only a single field of the record
was used for ordering.) Reimplement the `BstSet`

abstraction as a
functor parameterized on a structure that enables client-provided
comparison operator(s), much like the standard library `Set`

.

□

##### Exercise: efficient traversal [✭✭✭]

Suppose you wanted to convert a tree to a list. You'd have to put the values stored in the tree in some order. Here are three ways of doing that:

*preorder*: each node's value appears in the list before the values of its left then right subtrees.*inorder*: the values of the left subtree appear, then the value at the node, then the values of the right subtree.*postorder*: the values of a node's left then right subtrees appear, followed by the value at the node.

Here is code that implements those *traversals*, along with
some example applications:

```
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
let rec preorder = function
| Leaf -> []
| Node (l,v,r) -> [v] @ preorder l @ preorder r
let rec inorder = function
| Leaf -> []
| Node (l,v,r) -> inorder l @ [v] @ inorder r
let rec postorder = function
| Leaf -> []
| Node (l,v,r) -> postorder l @ postorder r @ [v]
let t =
Node(Node(Node(Leaf, 1, Leaf), 2, Node(Leaf, 3, Leaf)),
4,
Node(Node(Leaf, 5, Leaf), 6, Node(Leaf, 7, Leaf)))
(*
t is
4
/ \
2 6
/ \ / \
1 3 5 7
*)
let () = assert (preorder t = [4;2;1;3;6;5;7])
let () = assert (inorder t = [1;2;3;4;5;6;7])
let () = assert (postorder t = [1;3;2;5;7;6;4])
```

On unbalanced trees, the traversal functions above require quadratic
worst-case time (in the number of nodes), because of the `@`

operator.
Re-implement the functions without `@`

, and instead using `::`

, such
that they perform exactly one cons per `Node`

in the tree. Thus the
worst-case execution time will be linear. You will need to add an
additional accumulator argument to each function, much like with tail
recursion. (But your implementations won't actually be tail recursive.)

□

##### Exercise: RB draw complete [✭✭]

Draw the perfect binary tree on the values 1, 2, ..., 15.
Color the nodes in three different ways such that (i) each
way is a red-black tree (i.e., satisfies the red-black invariants),
and (ii) the three ways create trees with black heights of
2, 3, and 4, respectively. The *black height* of a tree
is the maximum number of black nodes along any path from its
root to a leaf.

□

##### Exercise: RB draw insert [✭✭]

Draw the red-black tree that results from inserting the characters D A T A S T R U C T U R E into an empty tree. Carry out the insertion algorithm yourself by hand, then check your work with the implementation provided in lecture.

□

##### Exercise: standard library set [✭✭, optional]

Read the source code of the standard library `Set`

module.
Find the representation invariant for the balanced trees that it uses.
Which kind of tree does it most resemble: 2-3, AVL, or red-black?

□