English subtitles

← 14-12 Take 2

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Let's see what the "Take 2" algorithm would do if it's given this graph here.
  2. The algorithm of course doesn't know the minimum vertex cover,
  3. but I'd keep those vertices marked here to help you answer the next quiz.
  4. What I would like you to think about is, how many vertices from the minimum vertex cover,
  5. does the "Take 2" algorithm put into its solution in each loop?
  6. By loop I mean this part here.
  7. So each time that this part here is run, how many vertices that the "Take 2" algorithm
  8. puts into the vertex cover actually belong to the minimum vertex cover?
  9. I'm going to give you 5 choices for this.
  10. Is it something that we can't make a general statement about?
  11. Is it at least 1? Is it at most 1?
  12. Is it exactly 1? Or is it exactly 2?
  13. Please select the correct answer here.