A student asked some very sensible questions about Problem 3 in
Problem Set 2. Here they are:

> 1. We are asked to write a polytime algorithm for finding PM,
>    assuming G has a PM. Does this mean we have to find the explicit
>    edges which form the PM? For example, if {(1,2),(2,1),(3,3)} is a PM,
>    do we have to output this set through the algorithm? If not, what do
>    we have to output?

First, we don't assume that G has a perfect metching. If it has one, PM
outputs YES, but if it doesn't, PM outputs NO. 

Yes, you have to find the edges explicitly, and output them.

> 2. What does "black box" mean? I guess that we don't have to care about 
>    what this "black box" does and only need to call this procedure in our
>    algorithm. Is that right?

black box = a procedure that does a task correctly.
So the answer to your question is yes.

> 3. In question3, we assume G has one PM. Does this mean G has exactly one
>    PM or more than one? Or is it not a important factor in our algorithm?

Its possible there are several perfect matchings, and in that case your
program should output any one of them.

> 4. Do we write the pseudo code for our algorithm or describe the algorithm
>    in the simple text?

Up to you. You can model yourself on how we solved SKS using SKD in class.

>    
> 5. How do we know the algorithm is polynomial time? Do we have to give out 
>    proof?

The most natural algorithm for this problem is a simple algorithm, so it
should be evident that it is polytime. If it is not evident to you that
your solution is polytime, it probably won't be evident to the marker, in
which case you should provide an explanation.