## Is It Random Solution - Design of Computer Programs

• 0:00 - 0:04
[Norvig] And the answer is that every permutation has a non-zero probability,
• 0:04 - 0:06
but they don't all have the same probability.
• 0:06 - 0:08
And let's see how I discovered that.
• 0:08 - 0:11
I wrote some test code that generated this output,
• 0:11 - 0:16
and what I did is I gave it some example inputs, some example decks, that were very simple.
• 0:16 - 0:19
First I gave it the deck consisting of 3 items--a, b, and c--
• 0:19 - 0:23
and then I gave it the deck consisting of 2 items--a and b--
• 0:23 - 0:29
and I had it test for both shuffle algorithms--the correct algorithm and the teacher's algorithm.
• 0:29 - 0:34
I had it generate a few thousand decks, shuffle them,
• 0:34 - 0:38
and then figure out how many times each of the possible outcomes come out.
• 0:38 - 0:42
For 3 cards there's 6 possible permutations.
• 0:42 - 0:46
Both shuffle algorithms generated all 6.
• 0:46 - 0:52
For the correct shuffle algorithm you can see that they're all about 1/6 of the time.
• 0:52 - 0:58
1/6 of the time would be 16.6667%, and they're all pretty close to that.
• 0:58 - 1:01
For the teacher's shuffle algorithm, not so much.
• 1:01 - 1:06
Notice that the combination abc only shows up 5% of the time,
• 1:06 - 1:11
whereas some of the other combinations show up 27% of the time.
• 1:11 - 1:13
Not very good distribution of probability at all,
• 1:13 - 1:16
so there's something wrong with that algorithm.
• 1:16 - 1:20
And it's even more obvious when we just give it the trivial case of a 2-card deck.
• 1:20 - 1:24
With the correct algorithm it turns out to be exactly 50-50.
• 1:24 - 1:27
It might have been 49.1, 50.1.
• 1:27 - 1:31
This is just luck that it was exactly 50-50 in my simulation.
• 1:31 - 1:34
But with the teacher's algorithm, way off.
• 1:34 - 1:40
1/6 of the time you get ab, and 5/6 of the time you get ba.
Title:
Is It Random Solution - Design of Computer Programs
Description:

more » « less
Video Language:
English
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
01:41
 Udacity Robot edited English subtitles for Is It Random Solution - Design of Computer Programs Gundega edited English subtitles for Is It Random Solution - Design of Computer Programs Amara Bot added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot