Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 01-13 Installing Monitoring Devices Solution

Get Embed Code
1 Language

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

  1. And the answer to that is that we only need to install 2 devices--
  2. one up here and one down here.
  3. This one up here covers those 3 cables,
  4. and this one down here covers these 3 here, so this one is covered twice.
  5. But we need at least 2 devices to cover the whole network and actually,
  6. in this case, this is the only possible solution for this.
  7. But of course, a computer can't just see that 2 devices suffice.
  8. So Alice's algorithm 'trying all possibilities' would have to go through
  9. all of the possibilities that you could have of installing a device
  10. at a certain communication point or not installing one.
  11. So, in this case here, that would be 16 different possibilities
  12. if we give the communication points little letters here
  13. so we can better distinguish them.
  14. So Alice's algorithm 'trying all possibilities' would have to consider
  15. installing no device at all, which would of course not be a valid solution.
  16. It could try installing just a device at 'A' which, again, would not be a valid solution,
  17. and so on.
  18. And of course the algorithm would also find solutions that are valid
  19. but would use more than the minimum number of monitoring devices
  20. that are actually needed.
  21. But since the algorithm tries all possibilities, it will also find this solution here
  22. using just 2 devices.