English subtitles

← 02ps-02 Recurrence Relation

Get Embed Code
3 Languages

Showing Revision 2 created 11/07/2012 by podsinprint_user1.

  1. For this problem, we’re going to start off with a
  2. template for a recursively generated graph.
  3. What the template says, if we want one node,
  4. we just return a single node. For other values
  5. make a G1 and a G2 that are half the size and
  6. then we make login connections between G1
  7. and G2 by picking a random point and
  8. connecting it with a random node, another
  9. random node and connecting it with a random
  10. node et cetera and then return. So this has the
  11. recurrence relationship that only have node
  12. with zero edges and if we have N nodes, we
  13. get two times the number of nodes we have
  14. for a graph of half the size plus big data of log
  15. in and so what we want you to do is to solve
  16. this recurrence.
  17. But we’re going to do this one a little differently
  18. than some of our previous homework
  19. assignments. Instead of a multiple choice
  20. question, we want you to explain how to
  21. actually solve this. So below there is a form
  22. link and at that link you’ll see this question
  23. restated. What we want you to do is write up
  24. your answer, post in response to the form, get
  25. the link for your answer and then insert it here.
  26. I’ll give you an example to make this more
  27. clear. So here is the question on the form and
  28. you should write up your answer, some
  29. possible answers might be that T of N is data
  30. login, N login, any other function and then you
  31. should explain why you’ve answered like this.
  32. Or to submit your answer hit the link button,
  33. copy of the link, and there are few copy of the
  34. link pasted into the box here.