Return to Video

02ps-02 Recurrence Relation

  • 0:00 - 0:02
    For this problem, we’re going to start off with a
  • 0:02 - 0:04
    template for a recursively generated graph.
  • 0:04 - 0:06
    What the template says, if we want one node,
  • 0:06 - 0:08
    we just return a single node. For other values
  • 0:08 - 0:11
    make a G1 and a G2 that are half the size and
  • 0:11 - 0:13
    then we make login connections between G1
  • 0:13 - 0:16
    and G2 by picking a random point and
  • 0:16 - 0:19
    connecting it with a random node, another
  • 0:19 - 0:21
    random node and connecting it with a random
  • 0:21 - 0:25
    node et cetera and then return. So this has the
  • 0:25 - 0:27
    recurrence relationship that only have node
  • 0:27 - 0:30
    with zero edges and if we have N nodes, we
  • 0:30 - 0:34
    get two times the number of nodes we have
  • 0:34 - 0:37
    for a graph of half the size plus big data of log
  • 0:37 - 0:40
    in and so what we want you to do is to solve
  • 0:40 - 0:41
    this recurrence.
  • 0:41 - 0:43
    But we’re going to do this one a little differently
  • 0:43 - 0:44
    than some of our previous homework
  • 0:44 - 0:46
    assignments. Instead of a multiple choice
  • 0:46 - 0:48
    question, we want you to explain how to
  • 0:48 - 0:51
    actually solve this. So below there is a form
  • 0:51 - 0:53
    link and at that link you’ll see this question
  • 0:53 - 0:56
    restated. What we want you to do is write up
  • 0:56 - 0:58
    your answer, post in response to the form, get
  • 0:58 - 1:01
    the link for your answer and then insert it here.
  • 1:01 - 1:03
    I’ll give you an example to make this more
  • 1:03 - 1:05
    clear. So here is the question on the form and
  • 1:05 - 1:08
    you should write up your answer, some
  • 1:08 - 1:11
    possible answers might be that T of N is data
  • 1:11 - 1:17
    login, N login, any other function and then you
  • 1:17 - 1:21
    should explain why you’ve answered like this.
  • 1:21 - 1:24
    Or to submit your answer hit the link button,
  • 1:24 - 1:26
    copy of the link, and there are few copy of the
  • 1:26 - 1:30
    link pasted into the box here.
Tytuł:
02ps-02 Recurrence Relation
Video Language:
English
Team:
Udacity
Projekt:
CS215 - Intro to Algorithms
Duration:
01:31
podsinprint_user1 edited angielski subtitles for cs215 ps2 02 q 002
podsinprint_user1 added a translation

English subtitles

Revisions Compare revisions