0:00:00.000,0:00:04.000
Most of this problem is that it's going to involve building an improved search tree
0:00:04.000,0:00:06.000
for the vertex cover problem.
0:00:06.000,0:00:11.500
So in order to start off with that, let's go ahead and try building the naive approach
0:00:11.500,0:00:15.000
which is very similar to what you did in problem set 1, if you'd like to
0:00:15.000,0:00:17.000
take a look back at that very quickly.
0:00:17.000,0:00:19.000
Let's take a look at this.
0:00:19.000,0:00:23.500
I'd like you to fill in a function, recursive vertex cover, that takes an input graph,
0:00:23.500,0:00:29.000
which is a list of lists, and an assignment, which is a list of vertices that we cover
0:00:29.000,0:00:33.000
and then builds the search tree from that.
0:00:33.000,0:00:37.000
So what your code should do--first, it should check if it's still possible
0:00:37.000,0:00:39.000
to construct a valid vertex cover.
0:00:39.000,0:00:44.000
If not, you should return float inf, the Python expression for infinity.
0:00:44.000,0:00:48.000
If the assignment is a valid vertex cover, then you return the size of that cover.
0:00:48.000,0:00:53.000
Otherwise, I want you to find a vertex v that does not have an assignment.
0:00:53.000,0:00:57.000
And, once again, I'd recommend checking out the naive algorithm
0:00:57.000,0:00:59.000
you implemented in problem set 1
0:00:59.000,9:59:59.000
for a different NP problem that is very similar to this one.