$1.(8$ points$)$ Let $\backslash ($ B $\backslash )$ be an undirected bipartite graph with vertex sets $\backslash ($ V $\backslash )$ and $\backslash ($ U $\backslash )$ and edge set $\backslash ($ E $\backslash ).($A bipartite graph is a graph such that the vertex set can be partitioned into two sets such that every edge contains an endpoint from each set.$)$

A matching of a bipartite graph is a subset $\backslash ($ S $\backslash )$ of the edge set $\backslash ($ E $\backslash )$ such that each vertex is contained in at most one edge of $\backslash ($ S $\backslash ).$

You wish to find the number of edges in the matching with the maximum number of edges.

For example, suppose you have $\backslash ($ n $\backslash )$ employees and $\backslash ($ b $\backslash )$ jobs. You have a bipartite graph with $\backslash ($ n$+$b $\backslash )$ vertices. There is an edge connecting employee $\backslash ($ i $\backslash )$ and job $\backslash ($ j $\backslash )$ if employee $\backslash ($ i $\backslash )$ can perform job $\backslash ($ j $\backslash ).$ You wish to find the maximum number of jobs that can be performed $($assuming that each job requires exactly one person.$)$ You can assume that the graph is given as a list of edges.

Consider the following backtracking algorithm that will achieve this:

a$)$ Explain why the worst case runtime will give you a recurrence of

$\backslash [$

T$($m$)=2$ T$($m$-1)+$O$($m$)$

$\backslash ]$

where $\backslash ($ m $\backslash )$ is the number of edges.

b$)$ Describe how you can improve this algorithm to get a worst case runtime of

$\backslash [$

T$($m$)=$T$($m$-1)+$T$($m$-2)+$O$($m$)$

$\backslash ]$

where $\backslash ($ m $\backslash )$ is the number of edges