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

CSE 4705Fall 2019 Sample Midterm Exam
First Name: Last Name:
The1st InclassexaminationThursdayOctober17th,201925offinalgrade This is just a short sample exam. The real midterm will be 50100 longer.
Exam duration: 75 minutes
This examination has 3 questions. Answer all 3 questions. This examination has 3 pages.
Please do not write below this line.
Page 1 of 3

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 h10 h12 h8 h10
h5 h13
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 DepthFirst search
b 3 points Greedy BestFirst search
c 3 points UniformCost search
d 3 points A search
Page 2 of 3

2. Search
a 2 points DepthFirst search using iterative deepening can be made to return the same solution as BreadthFirst 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
c 2points ThesolutionpathfoundbyUniformCostsearchmaychangeifweaddthesamepos itive constant, c, to every arc cost.
A. True B. False
d 2 points A search will always expand fewer nodes than UniformCost search. A. True B. False
e 3points SupposeyouareusingaGeneticAlgorithm.Twoindividualsi.e.,candidatesolutions in the current generation are given by 8digit sequences: 14625723 and 85346761. What is the result of performing 1point crossover with a crosspoint 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 AGeneticAlgorithmincludingcrossover,mutationandnaturalselectionwherethe population size n1, would perform most like which of the following search methods select one:
A. Simulated annealing
B. Greedy Hillclimbing
C. A random walk
D. Nothing will change i.e., the initial individual will stay the same
End of exam

3. Game Playing Consider the following game tree. The root is a maximizing node, and children are visited left to right.
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 AlphaBeta 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.
Page 4 of 3