$[$Permutation Routing$]$ Let $n$ be a positive integer and let $N=2^n.$ A hypercube is a undirected

graph over the vertices $\{0,1,2,$dots,$N-1\}.$ Vertices $x,$yin$\{0,1,2,$dots,$N-1\}$ are connected by

an edge if and only if the Boolean representations of $x$ and $y$ differ in exactly one bit position.

In the permutation routing problem, every vertex in the hypercube has exactly one packet to

send to some other vertex and receives exactly one packet. The problem hence has an associated

permutation $$ on the set $\{0,1,2,$dots,$N-1\}$ such that every vertex $x$ sends a packet to $(x)$ and

receives a packet from ${}^{-1}(x).$

Every node can send and receive simultaneously. However, at each time step $($time is discrete for

this problem$),$ at most one packet can be sent along an edge. Hence if some vertex wants to send

two packets along the same edge, one packet has to wait till the next time step. The objective of

the permutation routing problem is to route all the packets in minimum number of time steps.

A natural algorithm for this problem is bit fixing. Consider a packet that needs to be sent from

$x($its current location$)$ to $y.$ Let $x=(x_{n-1},x_{n-2},$dots,$x_0{)}_2$ and let $y=(y_{n-1},y_{n-2},$dots,$y_0{)}_2.$

Let $i$ be the minimum index such that $x_i{y}_i($such an $i$ is guaranteed to exist if $xy).$ Let

$x^{\text{'}}=(x_{n-1},$dots,$x_{i+1},y_i,x_{i-1},$dots,$x_0{)}_2.$ Then the packet is sent along the edge $\{x,x^{\text{'}}\}.$ Observe

that the routing algorithm does not consider other packets for deciding its route. Such routing

algorithms are called oblivious routing algorithm. Then prove the following.

$($a$)[$Bit fixing is not good in worst case$]$ Give an instance of the problem where bit fixing

algorithm takes $(\frac{\sqrt[\phantom{2}]{N}}{n})$ time steps.

$($b$)[2-$Phase routing via random intermediate destination$]$ The idea to bypass worst case

instances is to first route packets to a random intermediate instances and then route them

to the actual destinations. Formally, for every vertex $x,$ let $(x)$ denote a random element

chosen from $\{0,1,2,$dots,$N-1\}.$ Now for every $x,$ we first route the packet for $x$ from $x$ to

$(x)$ and then from $(x)$ to $(x)$ using bit fixing. Prove that, on every instance, the expected

number of time steps that the modified algorithm takes is $O(n).$