CS 325
Midterm
Instructions: This exam is governed by the Emory Honor Code.
Show all of your work for full credit on each problem.
Name:
I understand and will adhere to the Emory Honor Code.
Signature:
Problem 1 (25 points): Search
Answer the following questions about the search problem shown below. Assume that ties are broken alpha-
betically. (For example, a partial plan S→X→Awould be expanded before S→X→B; similarly,
S→A→Zwould be expanded before S→B→A.) For questions that ask for a path, please give your
answers in the form S−A−C−G.
(a) (5pts) What path would breadth-first search (BFS) return for this search problem?
(b) (5pts) What path would uniform cost search (UCS) return for this search problem?
(c) (5pts) What path would depth-first graph search (DFS) return for this search problem?
(d) (6pts) What path would A* graph search, using a consistent heuristic, return for this search problem?
(e) (4pts) Given the following table of heuristics, circle the appropriate answers.
