And then this is to check through the try analysis for
the leader-election algorithm.
This is just go through the steps in that analysis for this simpler recurrence,
which is the number of rounds in the leader-election algorithm to see what
the outline term looks like for that.
So read Chapter Eight in the text.
Here are a couple experiments that you might do to validate the mathematical
results in this lecture or that are similar to what we've done before.
So one is draw some random tries.
So you draw, say, 10 random tries with 100 nodes and
compare their shapes to random binary search trees or random Catalan trees.
Another thing is to run experiments for
random tries to try to validate the analysis to get
a plot like the one in the text to show that running
time really is pretty close to N log base 2 of N.
And then write up solutions to those exercises from the book and
assignments to [COUGH] check your understanding of strings and tries.