Solution Set 1

Problem 1

1.A. A state is a complete A,B bipartite graph where A =< J and B > = K. An operator on state S is to add a vertex V to the hubs the graph, and to restrict the authorities to those vertices in S that have inarcs from V. The start state is the "graph" with no hubs and where every vertex is an authority. The goal state is a complete bipartite J,M graph where M > = K.

1.B. The branching factor is W. The depth of search is J. The size of the state space is certainly less than WJ

1.C. { C,F,G ; D,E}

1.D No, since the depth of the goal state is known.

Problem 2

2.A. A state is a complete A,B bipartite graph where A > = J and B =< K. An operator on state S is to add a vertex V to the authorities the graph, and to restrict the hubs to those vertices in S that have outarcs to V. The start state is the "graph" with no hubs and where every vertex is an authority. The goal state is a complete bipartite M,K graph where M > = J.

2.B. The branching factor is Z. The depth of search is K. The size of the state space is certainly less than ZK

2.C. The algorithm actually returns a 4,2 bipartite graph: { D,E,F,H; C,G}.

Problem 3

There is more than one way to do this. One can take a state to be either the state at the top of each iterations of the "repeat" loop. Then an operation combines the "choose" and the "either/or". Alternatively, one can take a state to be the state at any choice point. That is, there would be one state at the "choose" statement, and an operator corresponding to that choice followed by a different state at the "either/or" statement and an operator corresponding to one or the other branch. We will take the first approach.

3.A. A state is a complete A,B bipartite graph where A =< J and B =< K. An operator is either to add a hub or add an authorities, so that the graph remains complete. The start state is the empty graph. The goal state is a complete J,K bipartite graph.

3.B. The branching factor is V. The depth is J+K. The size of the state space is therefore at most VJ+K

Problem 4

For simplicity, let J=K.

Step 1: Construct a K,K complete bipartite graph. Let G be the set of hubs and H the set of authorities. Pick one hub and call it vertex A; pick one authority and call that vertex B.

Step 2: We now construct a second graph. For any N > 2K, let c1 ... cN be a set of hubs and x1 ... xN be a set of authorities connected according to the following rule: there is an arc from cP to xQ just if 0 =< (P-Q) mod N < 2K-1. It is not hard to show (a) that this has no K,K complete bipartite subgraph; (b) that algorithms 1 and 2 will run a very long time before finding that out.

Step 3: Make a copy of the graph in step 2. Label the hubs y1 ... yN and label the authorities d1 ... dN

Step 4: Join the three graphs together by identifying c1 with A and d1 with B.

Step 5: Order the vertices alphabetically, with A and B first.

Now, if you run algorithm 1, it will begin by trying to find a good set of hubs among the ci, spend a very long time at that, and only then move on to G;H. Similarly if you run algorithm 2, it will begin by trying to find a good set of authorities among the di.

However, if you run algorithm 3, it will