Tangled cable: Let's have a long cable, from both ends of which protrudes n wires. Each wire at the left end is connected to just one at the other end and we want to find out which one. To do this, we can use the following operations: (1) apply voltage to a given wire at the left end, (2) disconnect voltage from a given wire at the left end, (3) measure the voltage at a given wire at the right end. What is the best algorithm that uses these operations to find out what is connected to what. Could it be done with the divide and conquer method? In what time complexity? The only solution I could figure out is to check each cable with each cable until we find match and then repeat with next cable.

  • 1
    $\begingroup$ Does knowing a the endpoints of a given wire give you any information about another wire(s) ?? If not then the fastest algorithm would be $\Omega(n)$ $\endgroup$ – droptop May 30 at 17:05
  • $\begingroup$ what is the algorithm? $\endgroup$ – Rikib1999 May 30 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.