CSCI 3202代做、Java程序语言调试、Python，c++设计代写

日期：2020-10-11 11:28

CSCI 3202

Midterm Exam

Remote edition

Section number:

? RIGHT NOW! Include your name, student ID and section number on the top of your exam. If

you’re handwriting your exam, write this information at the top of the first page!

? You may use the textbook, your notes, lecture materials, and Piazza as recourses. Piazza posts

should not be about exact exam questions, but you may ask for technical clarifications and ask

for help on review/past exam questions that might help you. You may not use external sources

from the internet or collaborate with your peers.

? You may use a calculator.

? If you print a copy of the exam, clearly mark answers to multiple choice questions in the provided

answer box. If you type or hand-write your exam answers, write each problem on their own line,

clearly indicating both the problem number and answer letter. Start each new problem on a new

page.

? Mark only one answer for multiple choice questions. If you think two answers are correct, mark the

answer that best answers the question. No justification is required for multiple choice questions.

For handwriting multiple choice answers, clearly mark both the number of the problem and your

answer for each and every problem.

? For free response questions you must clearly justify all conclusions to receive full credit. A correct

answer with no supporting work will receive no credit.

? The Exam is due to Gradescope by midnight on Monday, October 12.

? When submitting your exam to Gradescope, use their submission tool to mark on which pages

you answered specific questions.

Problem Student Points Max Points

Discrete Search 35

Games 30

Short Response 20

Information 15

Total 100

1

2

(1) [35 points] For problem 1, refer to the following graph, with heuristic values h(n) depicted inside

each node in parenthesis. Consider the task of finding the shortest path from S to G, where step

costs to travel between two nodes are given as edge weights.

1A) [5 points] In what order would BFS expand the nodes of the graph? List all nodes that

are expanded and the order in which they are expanded. Assume that numeric nodes are

expanded lowest-first when an option exists.

1B) [5 points] In what order would DFS expand the nodes of the graph? List all nodes that are

expanded in the order in which they are expanded. Assume that numeric nodes are expanded

lowest-first when an option exists.

1C) [5 points] In what order would UCS expand the nodes of the graph? List all nodes that

are expanded in the order in which they are expanded.

1D) [5 points] In what order would A? expand the nodes of the graph? List all nodes that are

expanded in the order in which they are expanded.

3

1E) [5 points] Is the heuristic h on the graph admissible? If so, explain why. If not, explain for

which single state n you could change the values of h(n) to make everything admissible and

consistent. What range of values for h are possible to make this correction?

1F) [4 points] Suppose after making any adjustments that you’ve arrived at a consistent and

admissible heuristic h1(n). You then decide to use the new heuristic h2(n) = 2h1(n). Is the

A?

solution found using h2 guaranteed to be optimal? Justify your answer.

1G) [3 points] Provide a reason as to why using an inadmissible or inconsistent heuristic may be

a bad idea.

1H) [3 points] Provide a reason as to why using an inadmissible or inconsistent heuristic may be

a good idea.

4

(2) [30 points] Parts A-D refer to this game. We’re playing our favorite new game, “walls among us.”

In this game, we play as a noble space explorer, maintaining our 2-dimensional ship represented

by the 4x4 grid below. On our turn, we may move in one of the 4 cardinal directions, and must

move into an unoccupied square. Our opponent is attempting to sabotage us, and has sabotaged

the ship’s warp drive! We have to fix it, but our opponent is in the game, and plays as a brick

wall trying to block our way. On the wall’s turn, they also must move in one of the 4 cardinal

directions, and must also move to an unoccupied square. The game ends - with us as the victor

- when we move to the goal in the bottom-right corner of the map. The wall may never move to

that tile.

2A) [4 points] Assuming the engine might be located in different playthroughs to any tile on the

board, what is the size of the overall state space? The exact result should use the fact that

the wall can never overlap with either you or the engine.

2B) [10 points] Draw a game tree with one move for each player from the starting position

shown. Nodes in the tree represent game states (location of all agents and walls). Edges in

the tree connect successor states to their parent states. Draw only the legal moves.

5

2C) [4 points] On the shallow game tree of depth 2 from part 2B, what would we infer is the

value of the game? Use the score of ”number of warp drives reached by the player” as your

evaluation function.

2D) [4 points] If we were to consider a game tree of depth 16 - holding eight moves for each player

instead of only one - what would minimax compute as the value of the starting position of

the game? Explain your reasoning.

2E) [8 points] Consider the minimax tree below. Upward pointing triangles are MAX nodes,

downward pointing triangles are MIN nodes.

What are the minimax values associated with each node? Do not consider any pruning at

this point.

A: B: C: D:

E: F: G: H:

On the diagram of the tree, indicate clearly which branches/leaves are pruned when alphabeta

pruning is applied to this game tree. Assume that nodes are expanded from left-to-right

at each layer. Briefly justify how you know those branches/leaves can be pruned. Vague

responses along the lines of simply saying “alpha-beta pruning algorithm” will receive 0

points.

6

2F) [5 points (EXTRA CREDIT)]. Consider a non zero-sum representation of a game. In

this setup, player A’s utility is denoted as the first of two leaf numbers and player B’s utility

by the second. Fill in this non-zero game tree assuming that each player is acting optimally

to maximize their personal utility.

7

(3) [20 points] Other Searches. For each question, answer the prompt and provide at least one full

sentence of reasoning and justification. More than one sentence may be necessary.

3A) [4 points] In what situation(s) is Breadth First Search identical to Uniform Cost Search?

3B) [4 points] Is hill climbing guaranteed to find the optimal solution? Why or why not?

3C) [12 points] Suppose we were interested in using the genetic algorithm to find a solution or

solutions to the system given by: a + 5b + 6c ? 12d + e = 1204 for positive integers a, b, c, d, e.

Suppose your initial population consists of 100 lists of the form [a, b, c, d, e], where each term

is initialized as a random integer from 1 to 500.

Propose a working genetic algorithm for this problem. This includes: a fitness function to minimize

- so one that will return zero when at a valid solution - and a selection/breeding/mutation

scheme that will find valid solutions to the problem.

Proposed Fitness Function:

Proposed P(breeding) Function:

Proposed Breeding/Mutation Scheme:

8

4A) [15 points] Suppose we’re going to catch the Buff Bus, and want to decide when to go wait for

it. We decide to use the the linear loss function

Ll(d, x) = (

2(x ? d) x ≥ d

4(d ? x) x < d

.

4A) [7 points] We model the Buff Bus arrival times as an exponential random variable X that

arrives on average once per hour, so they have probability density function of f(x) = e

?x

for

x > 0 (note: this has mean of EX[x] = 1). Set up but don’t evaluate an integral or integrals

for the expected loss EX[L(d, x)].

4B) [4 points] In class we discussed some conditions where the expected value of including

uncertainty (EVIU) might be zero; do those apply here? Why or why not? What’s larger

in this problem, the expected value of perfect information (EVPI) or the EVIU? You do not

need to calculate the exact values but you may if you wish.

4C) [4 points] In the loss function above, are we considering it more costly to overestimate or to

underestimate? How do you know? Do you think this is a reasonable model for waiting-forthe-bus?