CISC 339 Artificial Intelligence Spring 2018 Department of Mathematics and Three hours, closed book Please write all problems which add up to 100 points. You have the entire this exam. work on your answers on this exam. The exam is open book and consists of 4 class period, 3 hours, to Problems (100 pts): l. Uniformed and Heuristic Search (25 pts): Consider the search space as illustrated below, S Start state G) Goal state 3 Step cost 3 h-6h-8 20 h-2e dh-4 G h-o h 5 Heuristic estimate 2 h=1 a. Derive the search tree. b. List the order in which the nodes are expanded for the following search strategies: i Breadth-first search, i Depth-first search, ii Uniform cost search, iv Greedy best-first search, v A* search. c. Compute the complexity of each search algorithm in part b. d. which one works the best? Is the heuristic function admissible? Explain the reason. CISC 339 Artificial Intelligence Spring 2018 Department of Mathematics and Three hours, closed book Please write all problems which add up to 100 points. You have the entire this exam. work on your answers on this exam. The exam is open book and consists of 4 class period, 3 hours, to Problems (100 pts): l. Uniformed and Heuristic Search (25 pts): Consider the search space as illustrated below, S Start state G) Goal state 3 Step cost 3 h-6h-8 20 h-2e dh-4 G h-o h 5 Heuristic estimate 2 h=1 a. Derive the search tree. b. List the order in which the nodes are expanded for the following search strategies: i Breadth-first search, i Depth-first search, ii Uniform cost search, iv Greedy best-first search, v A* search. c. Compute the complexity of each search algorithm in part b. d. which one works the best? Is the heuristic function admissible? Explain the reason