## ← Tangled Hypercube - Intro to Algorithms

• 2 Followers
• 18 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=kH-oFk054ZM" data-team="udacity"></div> ``` 3 Languages

Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. Here's our last random graph of this unit.
2. We're going to again generate a graph on n nodes recursively.
3. Same structure as before.
4. If there's 1 node, we just return that node.
5. Otherwise, we do it recursively.
6. So we generate a graph on n/2 nodes--call that G1.
7. We generate a graph on n/2 nodes and call it G2--different graph.
8. Now we randomly scramble the nodes in those two,
9. keeping the edges in their appropriate way.
10. Just consider them in a particular order.
11. Then we connect the first node in this ordering in G1 to the first node in this ordering in G2,
12. the second one in this ordering in G1 to the second one in G2,
13. third one to the third one, forth one to the forth one, and so on.
14. Now we get a set of edges that now breach across these two graphs,
15. and we call this G and return it.
16. So based on this random generation process we can ask,
17. what kind of graph structure did we make?
18. Is it a ring, a tree, a hypercube, or maybe none of these?