for number 1.9: would B be valid, making D the correct answer? A and C seem to be true, but B is confusing. Does anyone see why B for this answer would be true, so that "all of the above" can be satisfied?
for 1.15, C seems like a good option but there may be something missing. does anyone feel differently about this answer?
for 3.D are we assuming this graph is in one component? otherwise, is there a way to define a spanning tree for a graph with multiple components?
Whoops, for 1.9, it seems the correct answers are (a) and (c), not (b). I had intended (d) as the answer when I wrote it. Sorry about that.
For 1.15, (c) is the right answer. It can't be (b) alone, because that doesn't mention S, and it can't be (a) alone, since (a) doesn't talk about all solutions to P.
For 3.(d), the best answer would be something like "A spanning tree of a graph G is a tree, all of whose vertices and edges belong to G, and which includes every vertex of G. A spanning tree exists whenever G is connected." Or you could write, for instance, "A connected subgraph of G, which contains no cycles, and which includes all vertices of G."
For graphs with multiple components, there is a notion of "spanning forest" of G, which is a forest, contained within G, whose components are the same as the components of G.
Oh, also, our midterm was set up almost exactly like what was in the practice exam, can we expect the same thing to be true of the final or should we expect something closer to our midterm?
I believe that the Structure Theorem is not in our book, but we did discuss it in class. I think that the correct answer is (c) though, from my notes, the structure theorem is where you compact all of the strongly components of a directed graph.
Answers to the last few homeworks were discussed during lectures, and, I believe, during lab too.
The study guide document has answers to the practice exam, which I have just gone over, and made a small number of corrections to. I think the link to the study guide is under the "Final Exam" discussion thread.
for number 1.9: would B be valid, making D the correct answer? A and C seem to be true, but B is confusing. Does anyone see why B for this answer would be true, so that "all of the above" can be satisfied?
ReplyDeletefor 1.15, C seems like a good option but there may be something missing. does anyone feel differently about this answer?
for 3.D are we assuming this graph is in one component? otherwise, is there a way to define a spanning tree for a graph with multiple components?
Whoops, for 1.9, it seems the correct answers are (a) and (c), not (b). I had intended (d) as the answer when I wrote it. Sorry about that.
ReplyDeleteFor 1.15, (c) is the right answer. It can't be (b) alone, because that doesn't mention S, and it can't be (a) alone, since (a) doesn't talk about all solutions to P.
For 3.(d), the best answer would be something like "A spanning tree of a graph G is a tree, all of whose vertices and edges belong to G, and which includes every vertex of G. A spanning tree exists whenever G is connected." Or you could write, for instance, "A connected subgraph of G, which contains no cycles, and which includes all vertices of G."
For graphs with multiple components, there is a notion of "spanning forest" of G, which is a forest, contained within G, whose components are the same as the components of G.
Is there a solution set for the practice exam available so that I can check my answers? or is it already posted and I'm just crazy :P
ReplyDeleteOh, also, our midterm was set up almost exactly like what was in the practice exam, can we expect the same thing to be true of the final or should we expect something closer to our midterm?
ReplyDeleteFor question 1.20 it is talking about the "Structure theorem" was that in our book?
ReplyDelete@niallsc
ReplyDeleteI believe that the Structure Theorem is not in our book, but we did discuss it in class. I think that the correct answer is (c) though, from my notes, the structure theorem is where you compact all of the strongly components of a directed graph.
Thanks @Lucas, you wouldn't happen to know when that lecture took place do you?
ReplyDeleteI have it right after notes from lab on Assignment #6. So sometime around there...sorry, I unfortunately don't date my notes.
ReplyDeletewe covered directed graphs on 10/11, in case you didn't already find it.
ReplyDeleteAre there any solution sets for the last two homework assignments?
ReplyDeleteI found this a few days ago and I have been cherry picking answers from it. You guys might find it helpful.
ReplyDeletehttp://www.cs.uiuc.edu/~jeffe/teaching/algorithms/
I having a few different explanations of the same thing always seems to help me.
Structure Theorem - Oct.11
ReplyDeleteWe never got answers to HW8 & HW9 to study?
ReplyDeleteAnswers to the last few homeworks were discussed during lectures, and, I believe, during lab too.
ReplyDeleteThe study guide document has answers to the practice exam, which I have just gone over, and made a small number of corrections to. I think the link to the study guide is under the "Final Exam" discussion thread.