YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 13ps-03 Cover By Tree

Get Embed Code
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.