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.
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.)
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.