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