Return to Video

Circular Definitions - Intro to Computer Science

  • 0:00 - 0:03
    So how can we fix this problem? Well, the first thing
  • 0:03 - 0:06
    we should think about is, well, can we give a base case.
  • 0:06 - 0:09
    All right. All of the recursive definitions we had. We had a
  • 0:09 - 0:12
    way of stopping. So, we had a base case. Right. With, factorial,
  • 0:12 - 0:15
    we said, we are going to pre-define, that we know the value
  • 0:15 - 0:19
    of factorial when the input is 0. We know that the value
  • 0:19 - 0:22
    is 1. We are not going to define it, in terms of factorial.
  • 0:22 - 0:25
    We are going to note it's value. We did this for palindrome we
  • 0:25 - 0:29
    said, palindrome, we have a base case, when the input
  • 0:29 - 0:33
    string is an empty string, it's predefined as a palindrome We
  • 0:33 - 0:35
    don't have to do anything else. And we did this
  • 0:35 - 0:38
    for fibonacci, where we had two bases cases? But for all
  • 0:38 - 0:41
    these definitions, we had some starting point, that was not
  • 0:41 - 0:44
    defined in terms of thing we are defining. And that's why
  • 0:44 - 0:47
    it was good recursive definition, because we had the base case.
  • 0:47 - 0:51
    We don't have one here. So let's try to invent one.
  • 0:51 - 0:54
    Let's suppose that we made our base case. So if
  • 0:54 - 0:55
    we're going to fix this, what we need to do
  • 0:55 - 0:58
    is invent a base case. Maybe that will solve our
  • 0:58 - 1:01
    problem. So let's try and add a base case. So.
  • 1:01 - 1:05
    Suppose we assume we know the popularity of Alice and
  • 1:06 - 1:10
    sadly Alice is not very popular. Her popularity score is
  • 1:10 - 1:13
    a 1. So that looks like a base case, right
  • 1:13 - 1:16
    we define the base case for factorial for 0 for palindrome
  • 1:16 - 1:18
    for space. Let's pick Alice as our base case
  • 1:18 - 1:22
    now. And. That works like this for the mathematical
  • 1:22 - 1:24
    definition. For the python code, what we would need
  • 1:24 - 1:26
    to do is add the base case, as in a
  • 1:26 - 1:28
    statement. So we would insert a line here that
  • 1:28 - 1:35
    says that if p is Alice, return Alice's popularity
  • 1:35 - 1:38
    score which is our base case which is 1.
  • 1:38 - 1:41
    So this looks more like the recursive definitions we've seen.
  • 1:41 - 1:43
    Now we have a question. See if this
  • 1:43 - 1:47
    actually works. So the question is, would this definition
  • 1:47 - 1:52
    work? The possible answers are, only if everyone
  • 1:52 - 1:55
    is friends with Alice, only if no one is
  • 1:55 - 1:58
    friends with Alice, only if, from every person
  • 1:58 - 2:01
    in the network,. There's some way that you can
  • 2:01 - 2:05
    follow links that eventually reaches Alice. Only if there
  • 2:05 - 2:06
    are no cycles in the graph. So there's no
  • 2:06 - 2:09
    way to start from one person and end
  • 2:09 - 2:11
    up at the same person by following friendship's, by
  • 2:11 - 2:15
    following friendship links. And the final choice is no,
  • 2:15 - 2:18
    that there's really no situation where this works well.
タイトル:
Circular Definitions - Intro to Computer Science
概説:

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

English subtitles

改訂 Compare revisions