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

• podsinprint_user1
• podsinprint_user1