$(20$ points$)$ Let $A[1..n]$ be an array that stores a random permutation of

$1,2,$dots,$n,$ where $n=m^2$ for some positive integer $m.$ Let $M[1..m,1..m]$

be a $2$D array such that $M[i,j]=A[(i-1)m+j]$ for $i,$jin$[1,m].$

The neighbors of an entry $A[i]$ are defined as follows. If $i=1,$ then $A[2]$

is the neighbor of $A[1].$ If $i=n,$ then $A[n-1]$ is the neighbor of $A[n].$

Otherwise, the neighbors of $A[i]$ are $A[i-1]$ and $A[i+1].$

Similarly, for $i,$jin$[1,m],$ the neighbors of $M[i,j]$ consist of $M[a,b]$ such

that $(a,b)in\{(i-1,j),(i+1,j),(i,j-1),(i,j+1)\}\{(i,j)$:$i,$jin$[1,m]\}.$

$($a$)(10$ points$)$ For any iin$[1,n],A[i]$ is a local minimum if it is smaller

than all of its neighbors. For any $i,$jin$[1,m],M[i,j]$ is a local

minimum if it is smaller than all of its neighbors. Derive the expected

number of local minima in A and $M.$ Give the exact formulas; do not

use asymptotic notation. Show your steps.

Hint: Introduce indicator random variables for each $A[i]$ and $M[i,j].$

$($b$)(10$ points$)$ For any iin$[2,n-1],$ if $A[i]$ is smaller than one neighbour

and greater than the other neighbor, then $A[i]$ is a saddle point. For

any $i,$jin$[2,m-1],M[i,j]$ is a saddle point if is smaller than both

of its neighbors in the same row and larger than both of its neighbors

in the same column. Derive the expected number of saddle points in

A and $M.$ Give the exact formulas; do not use asymptotic notation.

Show your steps.