NAME: CMPSC 442
PSU Login ID: FINAL EXAM: 100 points FALL 2018
INSTRUCTIONS: Write your name and SID at the top of every page. Write your answers on the exam
sheet in the white space below the questions. When you finish, show your id when you turn in your exam.
Item Question Maximum Points Actual Points
1 1a 2.0
2 1b 2.0
3 1c 1.0
4 2 5.0
5 3a 5.0
6 3b 5.0
7 3c 5.0
8 3d 5.0
9 4a 5.0
10 4b 5.0
11 4c 5.0
12 4d 5.0
13 5a 5.0
14 5b 5.0
15 6a 5.0
16 6b 5.0
17 7a 5.0
18 7b 5.0
19 8 5.0
20 9a 5.0
21 9b 5.0
22 9c 5.0
TOTAL 100.0
NAME 2
PSU Login ID
1. In uninformed search, the frontier stores states that are available for expanding during
search. In breadth first search (BFS), consider the strategy for adding to and expanding
the frontier.
a. (2 points) Indicate how BFS starts (how the frontier is initialized). Write your
answer below.
b. (2 points) Indicate how nodes are added and expanded. Write your answer
below.
c. (1 point) Indicate how it terminates. Write your answer below.
2. (5 points) The tree below is a breadth first search tree, showing more of the search
space than is needed: the goal node is the one labelled I (circled in a thick black line).
Indicate in the table below the succession of frontiers through this tree, using the
indicated format: place the next node that is expanded in column 1, and place the new
frontier in column 2. Add rows as needed. For completeness and ease of grading, the
final row should show the goal state in column 1 and the word “Goal” in column 2.
NAME 3
PSU Login ID
Node to
expand
New List of
Frontier Nodes
A BCD
3. A good search heuristic can reduce the search complexity.
a. (5 points) Explain a strategy to find a good heuristic. Write your answer below.
Find the cost of a solution to a relaxed version of the search problem.
b. (5 points) Give one of the two example heuristics for the 8-puzzle problem given
in class. Write your answer below.
Two heuristics discussed in class are OOP (number of out-of-place
tiles) and MD (manhattan distance).
c. (5 point) Explain how your answer to 3b is consistent with the strategy.
In the 8-puzzle problem, a tile can move from A to B only if B is empty and B is
adjacent to A. OOP relaxes the problem to allow a move in one step from A
to any location B. The number of OOP tiles will never over-estimate
the cost to the goal. MD is the number of moves from A to B, always moving to
an adjacent square, not necessarily an empty one. MD will also never
overestimate the cost to the goal.
d. (5 points): Give the second example for the 8-puzzle problem, and explain which
is a better heuristic and why.
NAME 4
PSU Login ID
MD is better because it is more accurate; MD OOP and MD true cost.≥ ≤
4. Hill-climbing is a search method that evaluates the next move in a search, and is useful
when there is no way to specify the entire state space for a search problem. It always
moves to a nearby state if the successor state has a better evaluation than the current
state. It is very efficient because there is no need to store any data other than the current
state and the evaluations of nearby states. The drawback is that it can reach a local
maximum that is far from the global maximum. Hill climbing with random restart is
guaranteed to succeed, given unlimited restarts, but is therefore very inefficient in the
worst case.
a. (5 points) What is the search method studied in class that combines the
efficiency of hill-climbing with the completeness of random restart? Write your
answer below.
Simulated annealing
b. (5 points) What is the critical new parameter of this method called? Write your
answer below.
Temperature
c. (5 points) Describe how this parameter is used during the search.
The temperature parameter T controls whether a new state will be selected as
successor, even if it has a worse evaluation than the current state. T starts out
high, and is lowered gradually. The acceptance probability to choose a successor
state is always greater than 1 if the new state is better, and is always positive. It
decreases as T decreases, and as new states become increasingly worse.
d. (5 points) Explain how this parameter makes the search behavior different early
in the search versus late in the search.
The consequence of starting with a high T that is lowered gradually is that early
in the search, it is more likely that a worse state will be moved to, allowing
escape from local maxima. As the search continues, the probability of accepting
a worse state decreases. If T is lowered slowly enough, simulated annealing is
Complete.
NAME 5
PSU Login ID
5. Constraint Satisfaction Problems: A CSP has a finite set of variables Xi, Xi+1, . . . Xn, a
non-empty domain for each variable, and constraints that limit the values that variables
can take. In this problem, you will draw a constraint graph (part a), and apply arc
consistency (part b). This means you first check the consistency of every arc Xi-Xj after
you make an assignment to Xi, then for every Xj that loses a value, recheck its arcs
(other than Xi-Xj).
You just started working for a map maker
who gave you a practice exercise to color in
the seven western states of Utah, Arizona,
Nevada, Idaho, Wyoming, Colorado and New
Mexico. No two states sharing a border (a
measurable edge) can be the same color.
The three colors you have to chose from are
red, blue and green (RBG). Ignore all the
other states in the figure that have grey
shading.
a. (5 points) At the top of the next page, draw the constraint graph for the above
map coloring problem.
b. (5 points) Apply arc consistency to this problem. The provided table below shows
all 7 variables (U.S. states) in the columns, and the first row shows the initial
domain for each state (RGB). Using this table, first add a row where you make an
initial assignment of red (R), and eliminate values that are inconsistent with this
assignment as follows:
i. add a new row and assign a color to the most constraining state Si (if
multiple states are tied for most constraining, select the state that is
leftmost in the table);
ii. circle the value you assigned;
iii. in the last column list all the arcs Si-Sj that need to be checked for
consistency given the assignment to Si;
iv. enter the new domains for the variables Sj connected to Si to make them
consistent.
v. Having added one row for an assignment to one variable, and all the arcs
involving that one variable, now do further consistency checking as
NAME 6
PSU Login ID
follows: add a row to show the new domains for any states that needed
consistency checking due to an Sj from the previous row whose domain
was reduced;
vi. list the relevant arcs Sj-Sk in the ARCS column.
vii. Repeat steps i through vi until you reach a solution, or find there is no
solution.
At row 3, the next most constraining states after UT are all the others but NM, so the tables
show assignments for picking NV first, ID first, etc
Pick NV’s color in row 3 = B
NV ID WY CO AZ UT NM ARCS
# RBG RBG RBG RBG RBG RBG RBG
1 BG BG BG BG BG R RBG UT-AZ,UT-NV,UT-ID,UT-WY,UT-C
O
2 BG BG BG BG BG R RBG No change
3 B G BG BG G R RBG NV-ID, NV-AZ (tied NV, ID, WY, CO, AZ)
4 B G B G G R R ID-WY, WY-CO, NM-WY, NM-AZ
Pick NV’s color in row 3 = G
NV ID WY CO AZ UT NM ARCS
# RBG RBG RBG RBG RBG RBG RBG
1 BG BG BG BG BG R RBG UT-AZ,UT-NV,UT-ID,UT-WY,UT-C
O
2 BG BG BG BG BG R RBG No change
NAME 7
PSU Login ID
3 G B BG BG G R RBG NV-ID, NV-AZ (tied NV, ID, WY, CO, AZ)
4 G B G B B R R ID-WY, WY-CO, NM-WY, NM-AZ
6. The syntax of first order logic (FOL) differs from predicate logic in that along with
constants (Mary, William) and connectives ( ), FOL syntax has predicates, ¬ ⋁ ⋀ ⇒ ⇔
functions, variables, equality and the two quantifiers ( ). ∃∀
a. (5 points) Translate the following English sentences into FOL.
Every dog barks.
x dog(x) ark(x)∀ ⇒ b
Some birds speak.
x bird(x) peak(x)∃ ⋀ s
b. (5 points) Translate the following FOL expressions into English.
x ∃y person(x) person(y) dmire(x, y)∀ ⋀ ⋀ a
Everyone admires someone.
x ∀y mountain(x) person(y) climb(y, x) ∃ ⋀ ⋀ ¬
There is a mountain no one has climbed.
7. For any finite, discrete events a and b, their probabilities are in the range [0,1]:
and similarly, , (a) 0 ≤ P ≤ 1 (b) 0 ≤ P ≤ 1
a. (5 points) Which of the following is true?
i. (a ) P (a) P (b) P (a )P ⋀ b = + − ⋁ b
ii. (a ) P (a) P (b) P (a )P ⋁ b = + − ⋀ b
b. (5 points) If and , which of the following statements about(a) 0.6P = (b) 0.1P =
cannot be true:(a )P ⋀ b
i. (a ) 0P ⋀ b =
ii. (a ) 0.1P ⋀ b <
iii. (a ) 0.6P ⋀ b <
iv. (a ) 0.1P ⋀ b >
NAME 8
PSU Login ID
A C P(B)
T T
T F
P(A) F T P(C)
F F
D P(E)
T
F
8. (5 points) In a Belief Net, each node is a random variable, and the directed edges
represent conditional dependence of children on their parents, and conditional
independence of all other random variables. In the above Belief Net composed of 5
random variables, each is binary, meaning it takes on the value True or False. E is
conditionally dependent on D, D is conditionally dependent on A and on B and on C, and
B is conditionally dependent on C and A. Next to each node, show its CPT (conditional
probability table) that specifies all the distinct possibilities for each child node conditioned
on its parents. That is, ignoring the actually probability values for each possible
combination of parents’ values, indicate the columns and rows needed for each node’s
CPT, by showing the combination of values for each row.
NAME 9
PSU Login ID
9. CKY parsing requires a binarized grammar, meaning a context free grammar in
Chomsky Normal Form.
a. (5 points) A context free grammar is a 4-tuple (N, , R, S). Define each memberΣ
of this tuple. Use the space below.
N a set of non terminal symbols
a set of terminal symbols (disjoint from N)Σ
R rewrite or production rules A where is a string from (N )*β→ β ⋃ Σ
S a start symbol
b. (5 points) CKY parsing (short for Cocke-Kasami-Younger) is an example of a
dynamic programming algorithm that uses a chart. Explain the constraint that all
grammar rules must meet to count as “binarized” and why CKY parsing requires
the grammar to be in this form.
In a binarized CFG, all rewrite or production rules are one of the following:
a) a non-terminal symbol on the LHS and a single terminal on the right hand
side
b) a non-terminal symbol on the LHS and exactly two non-terminal symbols
on the right hand side
NAME 10
PSU Login ID
c. (5 points) Given the sentence “The winger passed the striker kicking the ball”
draw a CKY chart for parsing this sentence in its initial form showing the upper
diagonal, the indices on the horizontal and vertical dimensions for keeping track
of substrings, and fill in three cells (upper left region) that show Terminal →
Non-terminal rules applied to the first two words “the” and “winger,” and the
application of a rule of the form Terminal Non-terminal1, Non-terminal2 to the→
entire phrase “the winger.” (Note: “winger” and “striker” are soccer positions.)