Question 1 – Sample Runs

Copy and paste the results of running each of the commands below:

Words in file order (sorted)

./minispell -f -d ../../data/ispell.words ../../data/smalldict.words

Words in shuffled order

./minispell -s -d ../../data/ispell.words ../../data/smalldict.words

Words in special well-balanced order

./minispell -b -d ../../data/ispell.words ../../data/smalldict.words

Question 2 – Comparisons

By what multiplicative factor was the average depth of the tree worse for the in-file-order insertion (which was sorted order) compared to the carefully chosen insertion-order that made a well-balanced tree?

Sorted Order was X times worse than Well-Balanced Order, where X is:

By what multiplicative factor was the average depth of the tree worse for the shuffled insertion (which was random order) compared to the carefully chosen insertion-order that made a well-balanced tree?

Shuffled Order was X times worse than Well-Balanced Order, where X is:

The file ../data/web2 has 234,937 words, rather than the 34,831 words found in ../data/ispell.words. (You can run experiments using this file if you like, but some tests might take a long time.)

Would you expect the multiplicative factor for in-file-order insertion (which is sorted order) compared to balanced insertion to be better, worse, or the same for this file?

Would you expect the multiplicative factor for shuffled-order insertion compared to balanced insertion to be better, worse, or the same for this file?

Briefly explain these two answers.

Question 3 – Worst-Case Behavior

A random tree with $$n$$ nodes has a worst-case average depth of $$$\frac{n-1}{2}$$$ and a worst-case height of $$$n-1.$$$

How close were you able to get to this worst-case with shuffled insertion with these word lists?

Briefly explain your answer.