[SOLVED] C algorithm game CSE 4705 Fall 2019 Sample Midterm Exam Solutions

CSE 4705 Fall 2019 Sample Midterm Exam Solutions
1. StateSpaceSearchConsiderthefollowingsearchtreeproducedafterexpandingnodesAandB,where each arc is labeled with the cost of the corresponding operator, and the leaves are labeled with the value of a heuristic function, h. For uninformed searches, assume children are expanded left to right. In case of ties, expand in alphabetical order.
A
3 19 5 BCD
4556 EFGH h=10 h=12 h=8 h=10
h=5 h=13
Figure 1: A search space after expanding nodes A and B. Which one node will be expanded next by each of the following search methods?
(a) [3 points] Depth-First search
(b) [3 points] Greedy Best-First search
(c) [3 points] Uniform-Cost search
(d) [3 points] A* search
2. Search
(a) [2 points] Depth-First search using iterative deepening can be made to return the same solution as Breadth-First search.
A. True B. False
(b) [2 points] In a finite search space containing no goal state and all states are reachable from the start state, A* will always explore all states.
A. True B. False
Solution: E
Solution: C (smallest h value)
Solution: D (smallest g value)
Solution: G (smallest g+h value)
Page 1 of 3

(c) [2points] ThesolutionpathfoundbyUniform-Costsearchmaychangeifweaddthesamepos- itive constant, c, to every arc cost.
A. True B. False For example, say there are 2 paths S -> A -> G and S -> G where cost(S,A) = 1, cost(A,G) = 1, and cost(S,G) = 3. So the optimal path is through A. If we now add 2 to each cost, the optimal path goes directly from S to G and UCS will now find this new path.
(d) [2 points] A* search will always expand fewer nodes than Uniform-Cost search. A. True B. False
(e) [3points] SupposeyouareusingaGeneticAlgorithm.Twoindividuals(i.e.,candidatesolutions) in the current generation are given by 8-digit sequences: 14625723 and 85346761. What is the result of performing 1-point crossover with a cross-point between the third and fourth digits?
(f) [3 points] If there are n individuals in the current generation, how many crossover operations are used to produce the next generation?
(g) [3points] AGeneticAlgorithm(includingcrossover,mutationandnaturalselection)wherethe population size n = 1, would perform most like which of the following search methods (select one):
A. Simulated annealing
B. (Greedy) Hill-climbing
C. A random walk
D. Nothing will change (i.e., the initial individual will stay the same)
Since n = 1, crossover will do nothing since the one parent will be selected twice and the generated child will be the same as its parents. Then, mutation is applied to the child copy of the parent, which will randomly modify the child with a small probability, causing it to have either higher or lower fitness than its parent. So, the algorithm will do a random walk in the space of individuals.
3. Game Playing Consider the following game tree. The root is a maximizing node, and children are visited left to right.
Solution: 14646761 and 85325723
Solution: Iftherearenindividualsinthecurrentgeneration,thenthereshouldbenindivid- uals in every generation. Crossover takes two individuals from the current generation and generates two children in the next generation. Hence n/2 crossover operations are used.
Page 2 of 3

Ignoring the values given above at the leaf nodes, could there possibly exist some set of values at the leaf nodes in the above tree so that Alpha-Beta pruning would do the following. Answer either Yes or No.
(a) [2 points] Pruning occurs at the arc from D to K.
(b) [2 points] Pruning occurs at the arc from E to M.
(c) [2 points] Pruning occurs at the arc from C to G.
(d) LabeltheMAXandMINnodesinthetreeastheywouldbelabeledbytheMINIMAXalgorithm.
Solution: No
Solution: Yes
Solution: No
End of exam