$(20$ points$)$ A d$-$dimensional box with dimensions $($x$1,$ x$2,...,$ xd$)$ nests

within another box with dimensions $($y$1,$ y$2,...,$ yd$)$ if there exists a permu$-$

tation $\backslash$pi on $\{1,2,...,$ d$\}$ such that x$\backslash$pi $(1)<$ y$1,$ x$\backslash$pi $(2)<$ y$2,...,$ x$\backslash$pi $($d$)<$ yd$.$

$($a$)(5$ points$)$ Show that the nesting relation is transitive and acyclic.

$($b$)(5$ points$)$ Let B$1$ and B$2$ be two given boxes. Describe an efficient

method to determine whether B$1$ nests within B$2.$ Explain the cor$-$

rectness of your method and its running time.

$($c$)(10$ points$)$ Consider n d$-$dimensional boxes B$1,$ B$2,...,$ Bn$.$ Describe

an efficient algorithm to find the longest sequence $($Bi$1,$ Bi$2,...,$ Bik $)$

of boxes such that Bij nests within Bij$+1$ for j $=1,2,...,$ k $1.$

Derive the running time of your algorithm and express it in terms of

n and d$.$ Marks will be deducted if your algorithm does not work in

a reasonably efficient manner.