$[1\mathrm{.}4][5$ marks$]$ The numpy module contains functions to generate random permutations. Given a non$-$negative integer n$,$ every permutation of $2$n

numbers can be turned into a matching by taking the first n half of the permutation entries $($i$.$e$.,$ the first n numbers$)$ and connecting each of them to the corresponding entry in the second half $($i$.$e$.,$ the last n numbers$).$ Use this method to write a function random$\_$matching that takes n and returns a randomly selected matching of $2$n numbers in the form of a list of n tuples, where each tuple contains two integers.

Note: Ensure that the tuples are returned such that the first integer is less than the second integer.

To demonstrate that your code works, draw the arc diagrams for five randomly chosen matchings of $20$

numbers.

$$

$$

$$

$$

$[1\mathrm{.}5][5$ marks$]$ The moduletimeit $($imported above$)$ allows you to compute the time a function call takes. Verify your answer about the time complexity from Exercise $[1\mathrm{.}3]$ by computing the run time for randomly chosen arc diagrams of suitable sizes and producing an appropriate plot of the average run times against the lengths of the matchings.

Interpret your results.

$$

$$

$$

$$

$[1\mathrm{.}6][5$ marks$]$ Now that you understand the code well, here is an alternative function written by some crazy Python programmer who loves to write one$-$line lambda functions.

countcrossnest $=$ lambda arcs: tuple$($map$($sum$,$zip$(*([($False$,$False$)]+[($i