Return to Video

Circular Definitions Solution - Intro to Computer Science

  • 0:00 - 0:05
    So the answer is no, that even with any
  • 0:05 - 0:08
    of these restrictions, we still don't have a good
  • 0:08 - 0:11
    definition. So, let's consider all the restrictions. So, the
  • 0:11 - 0:14
    first one was, if everyone is friends with Alice. So
  • 0:14 - 0:16
    that would only work if they don't have any
  • 0:16 - 0:19
    other friends. Let's say this is Alice. We've got
  • 0:19 - 0:23
    Bob and Charlie. They're both friends with Alice. But
  • 0:23 - 0:25
    Bob is also friends with Charlie and Charlie is friends
  • 0:25 - 0:30
    with Bob. That means that to figure out the popularity of
  • 0:30 - 0:33
    Bob we need to know the popularity of Charlie. To figure
  • 0:33 - 0:35
    out the popularity of Charlie we need to know the popularity
  • 0:35 - 0:38
    of Alice as well as the popularity of Bob. So we're never
  • 0:38 - 0:40
    going to get to a solution. We are going to keep
  • 0:40 - 0:44
    bouncing back and forth between Bob and Charlie doing this. The
  • 0:44 - 0:47
    second choice only if no one is friends with Alice. Well,
  • 0:47 - 0:51
    if no one was friends with Alice, that would remove these links.
  • 0:51 - 0:54
    It doesn't solve our problem. We're still not going to be able
  • 0:54 - 0:57
    to give a popularity score for Bob and Charlie. The third choice
  • 0:57 - 1:00
    only if there is a friendship path from everyone in the graph
  • 1:00 - 1:05
    that eventually reaches Alice. So adding this link would provide that property,
  • 1:05 - 1:07
    but it still doesn't solve our problem. It doesn't give us a
  • 1:07 - 1:10
    way to figure out the popularity of Charlie, because to know that,
  • 1:10 - 1:12
    we need to know the popularity of Bob, which we need to
  • 1:12 - 1:15
    know the popularity of Charlie for. We still end up in this cycle.
  • 1:16 - 1:19
    The final choice seems, possibly more promising. It says
  • 1:19 - 1:21
    there are no cycles in the graph, so if
  • 1:21 - 1:25
    we want to remove this cycle. We could do
  • 1:25 - 1:29
    this. In this case, we'd be okay, right? We could
  • 1:29 - 1:31
    figure out the popularity of Bob, by figuring out
  • 1:31 - 1:34
    the popularity of Charlie, which depends on the popularity
  • 1:34 - 1:38
    of Alice. Where we're not okay, is if Bob
  • 1:38 - 1:41
    has another friend. Let's say Bob is friends with Diana.
  • 1:41 - 1:44
    Well then, to figure out the popularity of Diana,
  • 1:44 - 1:47
    we need to know the popularity of Bob. Where
  • 1:47 - 1:50
    it breaks down is, suppose we also have Diana
  • 1:50 - 1:53
    and Edgar, and Diana's friends with Edgar. To figure out
  • 1:56 - 1:57
    the popularity score of Diana, we need to know the popularity score
  • 1:57 - 1:59
    of Edgar. We don't have a cycle, but we don't have an answer
  • 1:59 - 2:02
    either. To figure out the popularity of Edgar,. We are going to go through
  • 2:02 - 2:06
    Edgar's friends, and the way the Python code is written. This could actually
  • 2:06 - 2:11
    work, right? Because if we define popularity when you have no friends.
  • 2:11 - 2:13
    Well, if the friends of p is empty, when we go through this
  • 2:13 - 2:17
    loop, the score is going to be 0. So, if you answered there are
  • 2:17 - 2:21
    no cycles. That's at least worth credit for this, that could be correct.
  • 2:21 - 2:25
    In terms of the mathematical definition, it doesn't make very good
  • 2:25 - 2:27
    sense. We still needed a way to know the popularity of
  • 2:27 - 2:30
    Edgar. We've sort of defined things in this case to say,
  • 2:30 - 2:33
    if you have no friends, your popularity score is zero. And
  • 2:33 - 2:36
    the Python code will work for that. But it's not a
  • 2:36 - 2:41
    good way to define popularity. So its very arbitrary to say
  • 2:41 - 2:44
    we're going to make Alice the one whose popularity score is predefined
  • 2:44 - 2:47
    as one. There is nothing Alice could do to make herself
  • 2:47 - 2:48
    more popular. That's not very fair to
  • 2:48 - 2:51
    Alice and it doesn't give us meaningful scores.
タイトル:
Circular Definitions Solution - Intro to Computer Science
概説:

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS101 - Intro to Computer Science
Duration:
02:52

English subtitles

改訂 Compare revisions