Generating Random Paths. We would like to automate the planning of movement

for a robot situated in an m $$ n rectangular grid. Initially, the robot is located in the cell

at the North$-$East cornor of the grid $($the so$-$called initial position$),$ and the goal is to find

a path to the cell located at the South$-$West cornor of the grid $($the so$-$called goal position$).$

The robot can only make two types of movement: $($a$)$ move to the neighbouring cell South

of its current location, or $($b$)$ move to the neighbouring cell West of its current location.

$($a$)$ Design an algorithm that randomly generates a path for the robot, so that all paths from

the initial position to the goal position have an equal probability of being generated.

Analyze the running time of your algorithm, and express it in terms of m and n$.$

$($b$)$ Design an algorithm that takes an extra input $($i$,$ j$),$ and randomly generates a path that

starts at the initial position, then passes through cell $($i$,$ j$),$ and finally reaches the goal

position. $($You may assume that $1<$ i $<$ m and $1<$ j $<$ n$.)$ All paths fulfilling the

above requirement is generated with equal probability.