** Example: **
Suppose domino D1 has string ``bb" on top and string ``b''
on bottom; domino D2 has strings ``a'' and ``aab'' and domino D3 has
strings ``abbba'' and ``bb''. Then the ordering D2, D3, D2, D1 spells
out the string ``aabbbaabb'' both on the top and on the bottom.

- A
*state*is a sequence of dominos where either the top string is a prefix of the bottom string or the bottom string is a prefix of the top. For example, the sequence D2,D2 is a state since the top "aa" is a prefix of the bottom "aabaab". The sequence D2,D1 is not a state because the top is "abb" and the bottom is "aabb" and neither is a prefix of the other. - An operator on D1 ... Dk is to add another domino at the end, if that leads to a legitimate state.
- The start state is the empty sequence of dominos.
- The goal state is a non-empty sequence of dominos where the top string and bottom string are equal.

** Answer **

Empty ----> D1 -----> D1,D1 ----> D1,D1,D1 -----> D1,D1,D1,D1 | bb bbbb | bbbbbb | bbbbbbbb | b bb | bbb | bbbb | | | | | |--> D1,D1,D1,D3 | | bbbbbbabbba | | bbbbb | | | |--> D1,D1,D3 fails | bbbbabbba | bbbb | |-> D2 -----> D2,D2 fails a | aa aab | aabaab | |--> D2,D3 ----> D2,D3,D2 -----> D2,D3,D2,D1 aabbba aabbbaa aabbbaabb aabbb aabbbaab aabbbaabb

B. What happens if you try to use depth-first search over the state space in problem 1 to solve the example problem?

** Answer: ** You end up in the infinite branch D1,D1, etc. and
never find the solution.

empty -----> D1 -----> D1,D1 -----> D1,D1,D1 -----> D1,D1,D1,D1 bb | bbbb | bbbbbb | bbbbbbbb b | bb | bbb | bbbb | | | | | |--> D3,D1,D1,D1 | | abbbabbbbbb | | bbbbb | |--> D3,D1,D1 fails | abbbabbbb | bbbb | |--> D2,D1 -----> D2,D2,D1 fails abb | aabb aabb | aabaabb | |--> D3,D2,D1 ------> D1,D3,D2,D1 abbbaabb | bbabbbaabb bbaabb | bbbaabb | |--> D2,D3,D2,D1 aabbbaabb aabbbaabb(Note: It is just an odd coincidence that in both problems 1 and 2 the goal state is the rightmost state of the tree. This is not generally true in a BFS.)

** Answer:** At most N.

A. How could the description in problem 1 of a state be modified for this new problem?

** Answer: ** Add the condition that both the strings on the top and the
bottom must have length at most M.

B. I claim that this modified state space has a depth of at most M/K (rounding down). Give an argument justifying this claim.

** Answer: ** Either every string in the top of a domino has length
at least K, or every string in the bottom of a domino has length at
least K. In either case, if more than M/K dominos are used, the
either the string on top or the string on the bottom will have length greater
than M and will therefore be invalid. Since every operation adds a domino,
there can be at most M/K operations.

Give an upper bound on the size of this state space * in the general
case * (again, without reference to the particular example.)

** Answer: ** O(N^{M/K})

** Answer: **

D1 = a/ab D2 = ba/ab.There is an infinite path D1,D2,D2 ... However, there is no domino where the bottom is a suffix of the top or vice versa, so searching from right to left terminates immediately.