CMPSC442-2016-final-exam
NAME: CMPSC 442
SID: FALL 2016
FINAL EXAM: 100 points
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 have finished, show your id when
you turn in your exam.
QUESTION SCORE QUESTION MAXIMUM
1a 2.5
1b 5.0
1c 5.0
2a 5.0
2b 5.0
2c 5.0
3a 5.0
3b 5.0
3c 5.0
3d 5.0
3d 5.0
4a 5.0
4b 5.0
5 5.0
6a 5.0
6b 5.0
6c 5.0
7 2.5
8a 5.0
8b 5.0
8c 5.0
Total 100.0
NAME: CMPSC 442
SID: FALL 2016
2
Q1: [12.5 points] This question has 4 parts that differentiate Uniform Cost Search (UCS) from
Breadth First Search.
a) [2.5 points] How does UCS rank the frontier nodes of the search tree? (Multiple
choice)
a. Length of the path from the start node ni to the current node nj
b. Estimated length of path from the current node nj to the goal node
c. Cost of path from start node ni to the current node nj where the cost C(ni, nj) is
set to a fixed value
d. Cost of path from start node ni to the current node nj where the cost C(ni, nj) can
vary from pair to pair
b) [5 points] Why does uniform-cost search rank all the frontier nodes before checking
whether any of them is the goal?
.
c) [5 points] How does UCS terminate?
Q2: [15 points] Local search
a) [5 points] In local search, only the state space near the starting point is explored. How
does hill-climbing choose and evaluate a successor state?
b) [5 points] What type of state space landscape is a good fit for hill-climbing, and why?
c) [5 points] Name three kinds of landscape features that are a problem for hill-climbing
and why?
n∈N
NAME: CMPSC 442
SID: FALL 2016
3
Q3. [25 points] Minimax
In the minimax tree to the right, alpha beta pruning was utilized. Answer these questions:
a) [5 points] The value at node H
indicates the outcome will be (no
larger / no smaller) than 3.
b) [5 points] Node B is pruned
because:
c) [5 points] The value at node H
indicates the outcome will be (no
larger / no smaller) than 3.
d) [5 points] Node F is pruned because:
e) [5 points] Node G is pruned because.
Q4. [10 points] Constraint Satisfaction Propagation
You are in charge of scheduling for computer science classes that meet Mondays, Wednesdays
and Fridays. There are 5 classes that meet on these days and 3 professors who will be teaching
these classes. You are constrained by the fact that each professor can only teach one class at a
time.
The classes are:
• Class 1 – Intro to Programming: meets from 8:00-9:00am
• Class 2 – Intro to Artificial Intelligence: meets from 8:30-9:30am
• Class 3 – Natural Language Processing: meets from 9:00-10:00am
• Class 4 – Computer Vision: meets from 9:00-10:00am
• Class 5 – Machine Learning: meets from 9:30-10:30am
The professors are:
• Professor A, who is available to teach Classes 3 and 4.
• Professor B, who is available to teach Classes 2, 3, 4, and 5.
• Professor C, who is available to teach Classes 1, 2, 3, 4, 5
a) [5 points] Formulate this problem as a CSP problem with one variable per class; list the
domains; list the constraints.
Variables Domains Constraints
NAME: CMPSC 442
SID: FALL 2016
4
b) [5 points] Draw the constraint graph associated with this CSP.
Q5. [5 points] FOL. Fill in the last two columns of the following truth table.
T T T F
T T F T
T F T F
T F F T
F T T F
F T F T
F F T F
F F F T
Q6. [15 points] Conditional independence.
a) [5 points] A and B are conditionally independent given C iff
a.
b.
c.
b) [5 points] How many independent values are there in an exhaustive probability table with
3 binary random variables X, Y, Z.
c) [5 points] If X and Y are conditionally independent given Z, how many independent
numbers will there be?
Q7. [2.5 points] Smoothing
Name one disadvantage of add-one smoothing.
p q r ¬r p∨q p∨q→r
NAME: CMPSC 442
SID: FALL 2016
5
Q8. [15 points] Bayes Nets
The five random variables in the Bayes
Net on the right are Boolean variables:
B = BrokeElectionLaw
I = Indicted
M = PoliticallyMotivatedProsecutor
G = FoundGuilty,
J = Jailed
a) [5 points] Which, if any, of the
following are asserted by the network
structure (ignoring the CPTs for now)?
(i) P(B,I,M) = P(B)P(I)P(M)
(ii) P(J|G, I) = P(J|G)
(iii) P(M|G,B,I,J) = P(M|G,B,I)
b) [5 points] Calculate the value of P (b, ¬m, i, g, j)
c) [5 points] Calculate the probability that someone goes to jail given that they broke the law,
have been indicted, and face a politically motivated prosecutor.