1
00:00:00,012 --> 00:00:06,274
And let's finish up with several exercises
that you might do to cement your

2
00:00:06,274 --> 00:00:10,348
understanding of the material in this
lecture.

3
00:00:10,348 --> 00:00:15,892
So this is exercise 8.3.
So how long a string of random bits should

4
00:00:15,892 --> 00:00:21,400
you take if you want to have an even
chance that there's going to be 32

5
00:00:21,400 --> 00:00:27,586
consecutive zeros in that string.
So go ahead and calculate that number from

6
00:00:27,586 --> 00:00:33,184
information given in this lecture.
And this is a fun type of problem that

7
00:00:33,184 --> 00:00:37,324
leap was very fond of.
Suppose that a monkey types randomly at a

8
00:00:37,324 --> 00:00:41,644
32 character keyboard.
What's the expected number of characters

9
00:00:41,644 --> 00:00:46,636
that he's going to type before he hits on
the phrase, quick brown fox jumped over

10
00:00:46,636 --> 00:00:50,504
the lazy dog?
And we're going to have more complicated

11
00:00:50,504 --> 00:00:56,121
questions like that, that involve
repetition in the pattern as well.

12
00:00:56,122 --> 00:01:02,087
And then this is to check through the try
analysis for the leader election

13
00:01:02,087 --> 00:01:06,732
algorithm.
This is just go through the steps in that

14
00:01:06,732 --> 00:01:13,477
analysis for this simpler recurrence,
which is the number of rounds in the

15
00:01:13,477 --> 00:01:20,013
leader election algorithm to see what the
oscillating turn looks like for that.

16
00:01:20,013 --> 00:01:26,269
So read Chapter 8 in the text.
Here are a couple of experiments you might

17
00:01:26,269 --> 00:01:31,258
do to validate the mathematics results in
this lecture.

18
00:01:31,259 --> 00:01:35,041
Or that are similar to what we've done
before.

19
00:01:35,041 --> 00:01:41,011
So one is draw some random tries see and,
and draw a say ten random tries with 100

20
00:01:41,011 --> 00:01:46,807
nodes and compare their shapes to random
binary search trees or random Catalan

21
00:01:46,807 --> 00:01:51,488
trees.
Another thing is to run experiments for

22
00:01:51,488 --> 00:01:59,052
random tries to try to validate the
analysis to get a plot like the one in the

23
00:01:59,052 --> 00:02:07,013
text to show that the running time really
is pretty close to n log raise 2 of n.

24
00:02:07,014 --> 00:02:18,853
And then, write up solutions to those
exercises from the book assignments for to

25
00:02:20,323 --> 00:02:27,724
check your understanding the strings and
tries.