Problem 3: Wires and switches. You are given a black box that connects n wires to n switches. Each wire is connected to exactly one switch. Each switch is connected to zero or more wires. Your goal is to determine which wire is connected to each switch, without opening the box. You can perform a sequence of the following two operations: (1) Turn some switch j on or off. (2) ting a wire, if the switch it is connected to is on, then a lamp lights up. Wires Switches It is easy to discover all the connections using O(n) operations, as follows. Initially, turn all the switches off (n operations) For i = 1 ton For j = 1 ton Turn switch j on Test wire i If the lamp lights up we know that the wire i is connected to switch j Turn switch j off Give an algorithm which discovers all the connections using on log n) operations. Prove that your algorithm is correct and that the worst-case number of operations is O(n log n). Hint: Use divide conquer