## 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
 Udacity Robot edited 英語(米国) subtitles for 22-30 Circular Definitions Solution Udacity Robot edited 英語(米国) subtitles for 22-30 Circular Definitions Solution Udacity Robot edited 英語(米国) subtitles for 22-30 Circular Definitions Solution Cogi-Admin edited 英語(米国) subtitles for 22-30 Circular Definitions Solution

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API