## Solution Set 1

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.

### Problem 1

The problem can be characterized in terms of the following state space:
• 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.
A. Suppose you solve the above example problem using a breadth-first search. Show the state space that is generated. Assume that, where there is a choice, the algorithm tests dominos in numerical order (i.e. first D1, then D2 and so on.)

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.

### Problem 2

An alternative state space is to start at the end of the target sequence and to build backward, toward the front. As in Problem 1, show the state space generated using breadth-first search to solve the example problem.
```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.)

### Problem 3

For the general problem, if there are N dominos, what is the branching factor in the state space of problem 1? Please do NOT give an answer that relates to the characteristics of the particular example above.

Answer: At most N.

### Problem 4

Suppose that you modify the problem as follows: The input contains a number M in addition to the dominos, and the solution must contain at most M characters in the combined string. (E.g. in the example problem, there are 8 characters in the solution string "aabbaabb"). Let U be the length of the shortest string on the top of the dominos, let V be the length of the shortest string on the bottom of the dominos, and let K = max(U,V). (E.g. in the example problem, U = 1, corresponding to string "b" on D1; V = 1 corresponding to string "a" on D2; so K = 1.)

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(NM/K)

### Problem 5

Construct a sample problem where the state space in Problem 1 is infinite and the state space in problem 2 contains only the start space. (Hint: There is an answer to this question using only two dominos and where no string on the dominos is longer than two letters.)

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.
The text passage contains multiple problems and their solutions, each involving a specific question or task related to a state space and domino sequences. The questions are primarily about the structure and properties of the state space, and the answers are provided for each question.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
## Solution Set 1

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.

### Problem 1

The problem can be characterized in terms of the following state space:
• 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.
A. Suppose you solve the above example problem using a breadth-first search. Show the state space that is generated. Assume that, where there is a choice, the algorithm tests dominos in numerical order (i.e. first D1, then D2 and so on.)

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.

### Problem 2

An alternative state space is to start at the end of the target sequence and to build backward, toward the front. As in Problem 1, show the state space generated using breadth-first search to solve the example problem.
```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.)

### Problem 3

For the general problem, if there are N dominos, what is the branching factor in the state space of problem 1? Please do NOT give an answer that relates to the characteristics of the particular example above.

Answer: At most N.

### Problem 4

Suppose that you modify the problem as follows: The input contains a number M in addition to the dominos, and the solution must contain at most M characters in the combined string. (E.g. in the example problem, there are 8 characters in the solution string "aabbaabb"). Let U be the length of the shortest string on the top of the dominos, let V be the length of the shortest string on the bottom of the dominos, and let K = max(U,V). (E.g. in the example problem, U = 1, corresponding to string "b" on D1; V = 1 corresponding to string "a" on D2; so K = 1.)

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(NM/K)

### Problem 5

Construct a sample problem where the state space in Problem 1 is infinite and the state space in problem 2 contains only the start space. (Hint: There is an answer to this question using only two dominos and where no string on the dominos is longer than two letters.)

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.
user
The text passage contains multiple problems and their solutions, each involving a specific question or task related to a state space and domino sequences. The questions are primarily about the structure and properties of the state space, and the answers are provided for each question.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS