Return to Video

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

English subtitles

Revisions Compare revisions