Question 1:
Options 1 and 4 are correct. The belief state transition function results in a change to B
A x O x B —> B is correct (the left hand side can be any order)
B x A x O —> B is correct
B x O x A —> A is incorrect
A x B x O —> O is incorrect
Question 2:
Which of the following options are true.
NO: Breadth-first search is an implementation of the generic, uninformed search algorithm that implements the frontier as a stack
YES: Depth-first search is an implementation of the generic, uninformed search algorithm that implements the frontier as a stack
YES: If the branching factor of a breadth-first search is B, and the next path to be selected on the frontier has N arcs, then the frontier has O(B^N) elements.
From the text and the videos, it should be clear that breadth first search has an exponential space complexity in the depth of the search. With branching factor b, there are b^0 elements (1 element) at depth 0, with no arcs, just a path containing the start node); up to b^1 elements at depth 1 (each element of the frontier contains a path with one arc); up to b^2 elements at depth 2 (each path with two arcs; ….; up to b^N elements at depth N (each element with N arcs), etc
I found the paragraph in section 3.5.1 to be potentially confusing regarding specific numbers, with references to n-1, n, n+1 regards elements, paths, and arcs. Also, “at least b^(n-1) elements” stated as a lower bound, and then the potential for “n+1 arcs” as an upper bound stated in terms of ‘arcs’ or ‘paths’. This is why I used big-O notation to remove any ambiguity. b is regarded as a constant, and so b^(n-1), b^N, b^(N+1) are all O(b^N)
YES: Depth-first search is probably a good algorithm for finding a Starbucks in downtown Toronto. (see the first video on iterative deepening search at 45 seconds). This may seem like a silly question, but one goal of the quizzes is to ensure as best can that you are looking at the material — I didn’t think you were likely to forget the Starbuck’s reference if you watched the videos.