• Managing your videos in Amara teams just got easier! Read about it in our latest blog post. Hide

## ← 13ps-03 Cover By Tree

• 1 Follower
• 17 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=MIuDmIIZYpA" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

1. Most of this problem is that it's going to involve building an improved search tree
2. for the vertex cover problem.
3. So in order to start off with that, let's go ahead and try building the naive approach
4. which is very similar to what you did in problem set 1, if you'd like to
5. take a look back at that very quickly.
6. Let's take a look at this.
7. I'd like you to fill in a function, recursive vertex cover, that takes an input graph,
8. which is a list of lists, and an assignment, which is a list of vertices that we cover
9. and then builds the search tree from that.
10. So what your code should do--first, it should check if it's still possible
11. to construct a valid vertex cover.
12. If not, you should return float inf, the Python expression for infinity.
13. If the assignment is a valid vertex cover, then you return the size of that cover.
14. Otherwise, I want you to find a vertex v that does not have an assignment.
15. And, once again, I'd recommend checking out the naive algorithm
16. you implemented in problem set 1
17. for a different NP problem that is very similar to this one.