An $n-$polyomino is a plane shape formed by joining $n11$ squares edge to edge without overlapping.

Three data structures can be designed to represent a polyomino:

$($A$)$ Use a two$-$dimensional $LW$ array of digits, where $L$ and $W$ are the minimum length and width

that need to be used for storing the polyomino.

$($B$)$ Use a sequence of relative locations from any $11$ square within the shape.

$($C$)$ Use a tree representation with a clockwise pre$-$order traversal. That is$,$ we will treat each $11$

square in the polyomino as a node on the tree. One square will become the root of the tree. For

each of the rest squares, we assign one neighboring $($edge$-$sharing$)$ square as its parent. For each

square on the tree, we will use a $4-$bit indicator that depicts which neighboring cells are connected

to it in the tree. Finally, you record down these $4-$bit indicators of all tree nodes under a pre$-$order

traversal.

Problem $1$:

In this problem, we consider free polyominoes. That is$,$ two n$-$polyominos are

considered identical under translation, rotation, and flipping. Devise an efficient

algorithm such that, given two n$-$polyominoes $P$ and $Q,$ test if $P$ and $Q$ are

identical. Give a correctness proof and analyze the running time.

Hint: You may notice that we did not specify the "data structure" that represents

the input polyominoes. In the real world, this is indeed part of the algorithm

design when you are solving a relatively more complicated problem. Make sure

you specify which representation to use in your solution. $($l$.$e$.,$ choose the input

spec wisely.$)$ If you asked me$,$ I would choose the representation $($B$)$ from the

previous problem as the input format.

Problem $2$:

Devise an algorithm such that, given an integer $n,$ generates $($and counts$)$ all

distinct shapes of n$-$polyominoes. Give a correctness proof and analyze the

running time. Is your algorithm an exponential time algorithm? why or why not?

Hint: I will choose the representation $($C$)$ this time. Perhaps, we need a

subroutine that translates representation $($C$)$ to representation $($B$)$ so that the

algorithm you have developed from problem $1$ can be applied.