And let's finish up with several exercises
that you might do to cement your
understanding of the material in this
lecture.
So this is exercise 8.3.
So how long a string of random bits should
you take if you want to have an even
chance that there's going to be 32
consecutive zeros in that string.
So go ahead and calculate that number from
information given in this lecture.
And this is a fun type of problem that
leap was very fond of.
Suppose that a monkey types randomly at a
32 character keyboard.
What's the expected number of characters
that he's going to type before he hits on
the phrase, quick brown fox jumped over
the lazy dog?
And we're going to have more complicated
questions like that, that involve
repetition in the pattern as well.
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
oscillating turn looks like for that.
So read Chapter 8 in the text.
Here are a couple of experiments you might
do to validate the mathematics results in
this lecture.
Or that are similar to what we've done
before.
So one is draw some random tries see and,
and draw a say ten 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 the running time really
is pretty close to n log raise 2 of n.
And then, write up solutions to those
exercises from the book assignments for to
check your understanding the strings and
tries.