In case you're wondering, I put these three problems together, because, after the hints I gave in class yesterday, there would probably be less further discussion, compared to problem 2.8.
For 3.2, it asks us to return a cycle (if there is one). Suppose we had a graph with Nodes A,B,C and Edges (A,B),(B,C),(C,A). Would it be sufficient to return a list [A,B,C] or would [A,B,C,A] be more appropriate?
Either would be OK, but [A,B,C] is more usual. It is important that the vertices be given in their correct order around the cycle, but whether you list the starting vertex twice is not a big deal.
I'm assuming for the problems that say "give an algorithm" we're going to want to use DFS or BFS since they're already proven in the book to be O(m+n) time.
I'm kind of wondering how we can utilize these algorithms as a black box--and I've tried to already--since the G-S algorithm had a more clear output of the 1 to 1 stable matchings and I guess I'm not entirely sure what the BFS and DFS algorithms return. Do they return the BFS and DFS trees?
This would be easy to inspect the back edges, but it seems like we're going to have to do operations inside of DFS and BFS, does this sound right?
There isn't universal agreement about exactly what the output of BFS/DFS should be. If you want to think of them as outputting the search tree, or search forest, that is OK, just say so. Then you can use it as a black box, and just describe how to use the tree/forest to produce the desired answer.
On the other hand, you also want to know how to code these algorithms, and tweak the code to get it to do what you want, so I'm not recommending either approach above the other for these problems. Ideally, do both, to maximize your own understanding.
In case you're wondering, I put these three problems together, because, after the hints I gave in class yesterday, there would probably be less further discussion, compared to problem 2.8.
ReplyDeleteFor 3.2, it asks us to return a cycle (if there is one). Suppose we had a graph with Nodes A,B,C and Edges (A,B),(B,C),(C,A). Would it be sufficient to return a list [A,B,C] or would [A,B,C,A] be more appropriate?
ReplyDeleteEither would be OK, but [A,B,C] is more usual. It is important that the vertices be given in their correct order around the cycle, but whether you list the starting vertex twice is not a big deal.
ReplyDeleteI'm assuming for the problems that say "give an algorithm" we're going to want to use DFS or BFS since they're already proven in the book to be O(m+n) time.
ReplyDeleteI'm kind of wondering how we can utilize these algorithms as a black box--and I've tried to already--since the G-S algorithm had a more clear output of the 1 to 1 stable matchings and I guess I'm not entirely sure what the BFS and DFS algorithms return. Do they return the BFS and DFS trees?
This would be easy to inspect the back edges, but it seems like we're going to have to do operations inside of DFS and BFS, does this sound right?
There isn't universal agreement about exactly what the output of BFS/DFS should be. If you want to think of them as outputting the search tree, or search forest, that is OK, just say so. Then you can use it as a black box, and just describe how to use the tree/forest to produce the desired answer.
ReplyDeleteOn the other hand, you also want to know how to code these algorithms, and tweak the code to get it to do what you want, so I'm not recommending either approach above the other for these problems. Ideally, do both, to maximize your own understanding.