Intelligent Systems and Uninformed Search Strategies
1. [3 + 3 = 6 points] To what extent are the following computer systems instances of artificial intelligence: a. Supermarket barcode scanners
b. Web search engines
2. [6 points] Find the path from Source (S) to Goal (G), without passing through black squares using Depth-First Search (DFS). The successors are generated in order by moving UP, LEFT, RIGHT, and DOWN. You will number the squares according to the order of visit - starting from 1. Note that the goal test is performed when a node is generated.
G
S
3. [5 points] Considering the map of Romania, find the path from Arad to Bucharest, using uniform cost search. Give number, starting from 1, to each node in the order of expansion. You must show your work in detail using a tree to get the full credit.
4. [3 + 5 + 5 = 13 points] Consider the following search space below where S and G are starting and goal states, respectively. Perform a) Breadth First Search (BFS); goal test - when a node is removed from fringe, b) Uniform Cost Search, and c) Iterative Deepening Search (IDS) showing details using the following template table. Later mention the path and path cost according to these methods. Note that the order of nodes in the frontier/fringe matters.
Example: BFS – a few steps
Expanded node
Frontier list
{S}
S
{A, B, C}
A
{B, C, D, E}
B
{C, D, E, G}
