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?