Return to Video

Introduction - Intro to Algorithms

  • 0:00 - 0:05
    Hi and welcome back to unit4 of CS215.
  • 0:05 - 0:10
    We call this unit putting things in order or who is your 17th best friend.
  • 0:10 - 0:16
    So, by now, you might not be surprised that I actually have a magic trick worked out
  • 0:16 - 0:21
    that is, actually, in this case relevant to the topic at hand.
  • 0:21 - 0:28
    So, in this magic trick, I'm going to put a bunch of animals in order with your help.
  • 0:28 - 0:33
    So, here's some data, I have it stored as a Python structure at the moment.
  • 0:33 - 0:38
    We caught animals--it has 11 animals in it, alphabetized dog to sparrow,
  • 0:38 - 0:43
    and I've gone on the Internet and looked up the speed, how fast each of these animals is;
  • 0:43 - 0:46
    it's weight, approximately in kg;
  • 0:46 - 0:52
    Life span, how long they tend to live, and how big their brains are, measured in g.
  • 0:52 - 0:54
    I did not go and measured these animals' brains.
  • 0:54 - 0:59
    So, pretty common operation in social network analysis and lots of other problems
  • 0:59 - 1:02
    is to be able to put items in order.
  • 1:02 - 1:07
    So, in this particular case, we have a bunch of animals, we like to put them in order,
  • 1:07 - 1:09
    but there's lots of different dimensions on which to order them.
  • 1:09 - 1:14
    What we're going to do is we're going look at a linear combination of these numeric features,
  • 1:14 - 1:17
    and you're going to pick from me the weight, the positive weights,
  • 1:17 - 1:21
    to put on each of these different attributes and then we're going to take a sum,
  • 1:21 - 1:23
    in fact, I got the code right here for you to look at.
  • 1:23 - 1:30
    What I'd like you to do is run this code on this data and what you do is you call importance rank
  • 1:30 - 1:33
    on this data set animals and you give it the weights.
  • 1:33 - 1:39
    I gave a weight of 1 for the speed, 0.4 for the weight,
  • 1:39 - 1:45
    2 for the life span, and 0.1 for the brain mass.
  • 1:45 - 1:50
    So, if you would run it with this weights, it would actually compute a score for each of the animals
  • 1:50 - 1:54
    and then print them out in sorted order, but I want you to give your own weight.
  • 1:54 - 1:56
    Don't use mine because that wouldn't be very tricky with it.
  • 1:56 - 2:00
    Any weight you want just as long as they are not negative or zero.
  • 2:00 - 2:04
    But the program is going to print out are the numbers 0 through 10 for the 11 different animals
  • 2:04 - 2:08
    and I want you to make a note of, I don't know, let's say the fourth highest in the list,
  • 2:08 - 2:10
    the one that's associated with the number 3,
  • 2:10 - 2:14
    and I want you to make note of which animal appears in this position
  • 2:14 - 2:16
    and mark the corresponding circle.
  • 2:16 - 2:23
    And what makes this as a magic trick is that the algorithm that I'm using, the running time is so fast,
  • 2:23 - 2:28
    that it's θ(-n), that is to say I can compute the answer to this question
  • 2:28 - 2:32
    before you've asked the question--so, I've already run this.
  • 2:32 - 2:36
    I know what answer you're going to get, but now, you need to run it to make it so
  • 2:36 - 2:41
    and let's see if you're right.
Cím:
Introduction - Intro to Algorithms
Leírás:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS215 - Intro to Algorithms
Duration:
02:42
Udacity Robot edited Angol subtitles for Introduction - Intro to Algorithms
Gundega edited Angol subtitles for Introduction - Intro to Algorithms
Amara Bot hozzáadott egy fordítást

English subtitles

Felülvizsgálatok Compare revisions