1). (25 points). Consider the search tree shown in Figure 1. The number next to each edge is the cost of the performing the action corresponding to that edge. List the order in which nodes will be visited using:
Answer: Note that many answers are possible, here we only show one or two per type of search.
2). A social network graph (SNG) is a graph where each vertex is a person and each edge represents an acquaintance. In other words, an SNG is a graph showing who knows who. For example, in the graph shown on Figure 2, George knows Mary and John, Mary knows Christine, Peter and George, John knows Christine, Helen and George, Christine knows Mary and John, Helen knows John, Peter knows Mary.
The degrees of separation measure how closely connected two people are in the graph. For example, John has 0 degrees of separation from himself, 1 degree of separation from Christine, 2 degrees of separation from Mary, and 3 degrees of separation from Peter.
a). (10 points) From among breadth-first search, depth-first search, iterative deepening search, and uniform cost search, which one(s) guarantee finding the correct number of degrees of separation between any two people in the graph?
Answer: all except for depth-first search.
b). (10 points) For the SNG shown in Figure 2, draw the first three levels of the search tree, with John as the starting point (the first level of the tree is the root). Is there a one-to-one correspondence between nodes in the search tree and vertices in the SNG? Why, or why not? In your answer here, you should assume that the search algorithm does not try to avoid revisiting the same state.
Answer: the first three levels of the search tree are shown on Figure 2b. There is not a one-to-one correspondence between nodes in the search tree and vertices in the SNG, because loops can occur. For example, from Helen at the second level we get back to John at the third level.
Figure 2b. Answer to question 2b.
c). (10 points) Draw an SNG containing exactly 5 people, where at least two people have 4 degrees of separation between them.
Answer: In figure 2c, Peter and Helen have four degrees of separation between them.
Figure 2c. Answer to question 2c.
d). (10 points) Draw an SNG containing exactly 5 people, where all people have 1 degree of separation between them.
Answer: In figure 2d, all people one degree of separation between them.
Figure 2d. Answer to question 2d.
e). (10 points) In an implementation of breadth-first search for finding degrees of separation, suppose that every node in the search tree takes 1KB of memory. Suppose that the SNG contains one million people. Outline (briefly but precisely) how to make sure that the memory required to store search tree nodes will not exceed 1GB (the correct answer can be described in one-two lines of text). In your answer here you are free to enhance/modify the breadth-first search implementation as you wish, as long as it remains breadth-first (a modification that, for example, converts breadth-first search into depth-first search or iterative deepening search is not allowed).
Answer: Keep track of people already visited in the search, so that for every person in the graph we only keep one node in memory.
Consider greedy search, where the node to be expanded is always the one with the shortest Euclidean distance to the destination. Also consider A* search, where h(n) is the Euclidean distance from n to the destination (remember that the next node is picked not based on h(n) but based on f(n) = g(n) + h(n)). For each of the maps showing on Figures 3 and 4, which of the following statements is true?
Figure 3. A map of cities on a fully connected grid. Every city is simply named by its coordinates.
Figure 4. A map of cities on a partially connected grid. Every city is simply named by its coordinates.
Answer: For the map of Figure 3, best-first search will always perform either as well as A*, or better than A*. Best-first search will find immediately an optimal route, and will never expand nodes outside of that optimal route. A*, on the other hand, sometimes will be as good as best-first (for example going from (0,0) to (0,8)), and sometimes it will do worse. For example, going from (0, 0) to (8,8), A* will expand both (1,0) and (0,1), whereas best-first will only expand one of the two. For the map on Figure 4, depending on the start and end, best-first will perform worse, the same, or better, compared to A*. For example, best-first will perform better than A* for the route from (2, 6) to (5, 8), best-first will perform as well as A* for the route from (2, 6) to (2, 2), best-first will perform worse than A* for the route from (2, 0) to (2, 2) (where best-first will get stuck in an infinite loop).