Section 1 (Problems 1 – 3)

Consider the graph below.

•   Suppose A is the initial state, and Z the goal state.

•    Note that the graph is directed (e.g., we can go from A to C, but not from C to A).

•    Make any arbitrary choices as directed on p. 3.

1) (6 points) Pick one: In BFS (graph search), what is the order in which states would be expanded?

A) ○   A B C D E

B) ○   A B C D E Z

C) ○   A B C D C E D

D) ○   A B C D E C D Z

E) ○   A B C D C E D C Z

2) (6 points) Pick one: In BFS (graph search), what is the greatest number of states on the frontier at one time?

A) ○   1

B) ○   2

C) ○   3

D) ○   4

E) ○   5

Continuing with the same graph and instructions as the previous page, repeated here:

•   Suppose A is the initial state, and Z the goal state.

•    Note that the graph is directed (e.g., we can go from A to C, but not from C to A).

•    Make any arbitrary choices as directed on p. 3.

3) (9 points) Pick one: In DFS (tree-like search), what is the order in which states would be removed from the frontier?

A) ○   A B E Z

B) ○   A B C D E Z

C) ○   A D C B E Z

D) ○   A D C B E C D Z

E) ○   A B C D E C D Z

Section 2 (Problems 4 – 6)

Consider the graph below.

•   Suppose A is the initial state, and Z the goal state.

•    Note that the graph is undirected (in

contrast to the previous provided graph).

•    Make any arbitrary choices as directed on p. 3.

•   We’ll use the special notation for a node as described on p. 3.

4) (3 points) Pick one: Consider UCS (graph search). Suppose you expand Ato get the frontier:

AB3 AC7

Show the frontier resulting from the next expansion.

A) ○   ABC5 AC7

B) ○   ABC5 ACZ8

C) ○   ABC5 ABA6 AC7

D) ○   AC7 ABA6 ABC5

5) (3 points) True or False: A* with heuristic h above will find the cost-optimal solution.

A) ○   True

B) ○   False

6) (3 points) True or False: A* with heuristic h above will perform in an optimally efficient manner.

A) ○   True

B) ○   False

Section 3 (Problems 7 – 10)

Answer the following about breadth-first search

(not to be confused with “best-first search with a FIFO queue”).

7) (3 points) Pick one: Which of the following best describes the goal test?

8) (3 points) Pick one: Which of the following best describes the ideal reached data structure implementation?

9) (3 points) Pick one: When a solution node is returned, how can the corresponding path from initial state to goal be generated?

10) (3 points) Pick one: Suppose we were to implement the BFS frontier as a priority queue that selects the item with lowest f-cost. What must f(n) be?

Section 5 (Problems 11 – 12)

Consider the graph, with an unspecified h(C):

11) (8 points) Pick one or more: Among the values below, select all those that would result in h being admissible.

A) ○   2

B) ○   4

C) ○   6

D) ○   8

12) (8 points) Pick one or more: Among the values below, select all those that would result in h being consistent.

A) ○   2

B) ○   4

C) ○   6

D) ○   8

Section 6 (Problems 13 – 14)

In this section, consider path search algorithms in general, not necessarily applied to any specific graph given elsewhere in this exam. Also assume in this section the use of graph search, not tree-like search, for every algorithm (including Depth-First).

Suppose an agent is running a path search algorithm on a real-world (finite) map, to find a path from one city to another.

13) (9 points) Pick one or more: Select the path search algorithm(s) that is/are guaranteed to give the agent a cost-optimal path.

A) ○   Breadth-First

B) ○   Uniform Cost

C) ○   Depth-First

D) ○   Depth-Limited

E) ○   Iterative Deepening

F) ○   Greedy Best-First

G) ○   A* with an inadmissible heuristic

H) ○   A* with an admissible heuristic

I) ○   A* with a consistent heuristic

14) (9 points) Pick one or more: Consider the same scenario as the previous problem. Select the path search algorithm(s) that is/are guaranteed to find a path from one city to another if there is one.

A) ○   Breadth-First

B) ○   Uniform Cost

C) ○   Depth-First

D) ○   Depth-Limited

E) ○   Iterative Deepening

F) ○   Greedy Best-First

G) ○   A* with an inadmissible heuristic

H) ○   A* with an admissible heuristic

I) ○   A* with a consistent heuristic

Section 7 (Problems 15 – 20)

15) (3 points) Pick one: In a particular path search problem, suppose the only goal state is at a known depth, d. Consider Depth-Limited Search with a depth limit L. Which condition best describes what is required to find a path that contains the minimum number of

steps?

A) ○   d < L

B) ○   d ≤ L

C) ○   d = L

D) ○   d > L

E) ○   d ≥ L

16) (3 points) Assume all action costs are ≥ ∈ > 0. True or False: In Uniform Cost Search, the first time a node is expanded, that node has the smallest path cost to that state.

A) ○   True

B) ○   False

17) (3 points) Pick one: Consider a problem with a large state space that could be posed either as a systematic path search or as local search. Which of the following is a key advantage of local search algorithms over systematic search algorithms like A*?

A) ○   They are always complete.

B) ○   They always find the global optimum.

C) ○   They always terminate in polynomial time.

D) ○   They always use less memory.

18) (4 points) Pick one: Which of the following is FALSE about simulated annealing?

Section 8 (Problems 21 – 22)

In this section, consider the CSP: A with DA = {2, 3, 5}

B with DB = <domain not shown here> Constraint: B % A = 0

where % is the modulus (remainder) operator.

21) (12 points) Pick one or more: Among the possible values of DB listed below, choose all that would make B arc-consistent with respect to A.

A) ○   {6}

B) ○   {30}

C) ○   {8, 9, 25}

D) ○   {16, 21, 22, 35}

22) (12 points) Pick one or more: Among the possible values of DB listed below, choose all that would make A arc-consistent with respect to B.

A) ○   {6}

B) ○   {30}

C) ○   {8, 9, 25}

D) ○   {16, 21, 22, 35}