Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Popularity - Intro to Computer Science

Get Embed Code
4 Languages

Showing Revision 4 created 05/24/2016 by Udacity Robot.

  1. So here's a typical group of friends in middle
  2. school. And some of the people are popular, some of
  3. them might not be. The first step to deciding
  4. who's popular, is looking at who has a lot of
  5. friends. So let's draw in some links, that show
  6. who's a friend. And friendship links are one directional. Just
  7. because Alice's friends with Bob, doesn't mean that Bob
  8. is friend with Alice. So we'll draw our links as
  9. arrows, so this means this person, we'll call him Bob, is
  10. friends with Alice. And let's say, Alice
  11. has many friends. And let's say Bob is also friends with
  12. this person, they're friends with each other.
  13. We have lots of friendship links. Some
  14. of them are bi-directional but not all of them. So, we have lots of friendships.
  15. So, is this enough to decide who's popular. So, if you
  16. went to a school like I did, it's not. Just having a
  17. lot of friends is not enough to make you popular, you
  18. have to have the right friends. You have to be friends with
  19. the popular people. So, it's not enough to have lots of
  20. geeky friends say in high school, you've gotta have lots of friends
  21. that are popular. So that means the definition of popular, isn't
  22. just about having lots of friends, it's about having lots of friends,
  23. who also have lots of friends. That's what
  24. make some one popular, so we can define
  25. popularity of a person is the number of
  26. people who are friends with p. This means
  27. the number of links from someone else to
  28. that person is their popularity score. So here
  29. is Charlie, so there are one, two, three
  30. links into Charlie, so Charlie's popularity score would
  31. be three. Alice also has three links, so her
  32. popularity score would also be three. Bob only has one
  33. arrow going to Bob, so his popularity score would be
  34. one. So, this isn't a bad way to define popularity,
  35. but it's not quite right. So, the definition of popularity
  36. doesn't just depend on the number of friends you have,
  37. it depends on, both, the number, and the popularity of
  38. your friends. So, we can change the definition. Let's instead
  39. define the popularity score of a person p. Now
  40. it's going to be the sum of the popularities of
  41. all of their friends. So we can write that in
  42. a mathematical way, so using the sigma means to sum
  43. up. We're going to take each friend, that is in
  44. the friends of p. And we're going to sum up the
  45. popularity score of the friends. If the mathematical notation is
  46. unfamiliar to you, we could also write this as pseudo
  47. Python code. We're thinking of the popularity of
  48. a person p. Let's assume we have a
  49. function that gives us the friends. So we're
  50. going to start with a score of zero. We're going to
  51. loop through the friends. And for each friend,
  52. we're going to add to p score, the popularity score
  53. of the friend. And we'll return the score
  54. as the result. So now, you've seen a mathematical
  55. definition of popularity, you've seen the same thing as code. I'm going to ask
  56. you a very important quiz question next. Its an easy one to get
  57. right if you try it twice because there's only two answers, but think
  58. about it carefully. See if you can get it right the first time.