NAME: CMPSC 442
SID: FINAL EXAM: 100 points FALL 2017
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 Maximum Points Actual Points
1a 2.5
1b 2.5
1c 2.5
1d 2.5
1e 10.0
2a 2.5
2b 2.5
2c 5.0
2d 10.0
3a 2.5
3b 2.5
3c 10.0
4 25.0
5a 2.5
5b 2.5
5c 2.5
5d 2.5
5e 2.5
5f 2.5
5g 2.5
5h 2.5
TOTAL 100.0
NAME 2
SID
1. Uninformed Search (5 parts, 20 points total)
Search is evaluated by completeness, optimality, and space & time complexity.
1a. Define completeness (2.5 points) .
1b. Define optimality (2.5 points) .
1c . Space & time complexity are analogous; how are they different (2.5 points) ?
1d. What are the three aspects of an uninformed search algorithm used to express time
complexity and space complexity (2.5 points) ?
1e . Fill in the rest of the following table. Use big O notation for complexity. (10 points)
Breadthfirst Depthfirst Iterative Deepening
Complete
Optimal
Time
Space
2. Informed Search (4 parts, 20 points total)
2a. What is the definition of an admissible heuristic h (2.5 points)?
NAME 3
SID
2b. What is the definition of a consistent heuristic h (2.5 points)?
2c . What is a strategy to find a good heuristic for a search problem P (5 points)?
2d. Give an example of an admissible heuristic for the 8puzzle that we reviewed in class, and a
relaxation of the 8puzzle rules that the heuristic is a solution for (10 points).
3. Games and adversarial search (3 parts, 15 points total)
3a. In alphabeta pruning applied to minimax adversarial search, what does alpha keep track of
(2.5 points) ?
3b. What does beta keep track of (2.5 points) ?
NAME 4
SID
3c. Apply alpha beta pruning to the graph shown here: assign the number at each of the nodes
that the minimax algorithm with alpha beta pruning will pass up the tree. Mark through arcs that
are pruned away, if any, and nodes that are pruned away, if any. To mark an arc as pruned
away, place an = over the arc. To mark a node as pruned away, place an X over the node (10
points) .
4. Shiftreduce parsing (25 parts, 25 Total Points). Given the grammar rules shown below,
write out the steps in a shiftreduce parse for the following sentence: “Students at PSU are very
intelligent and hardworking.” The next page shows how to start. Fill in the remaining rows,
marking each row as S for Shift or R for reduce.
S → NP, VP
CONJ → “and”
NP → NNS
NP → NN
NP → PRO
NNS → “students”
NP → NP, PP
PP → PREP, NP
PREP → “at”
NP → NE
NE → “PSU”
VP → V,ADJP
ADJP → ADJP, CONJ, ADJP
ADJP → ADV, ADJ
ADJP → ADJ
ADV → “very”
ADJ → “intelligent”
ADJ → “hardworking”
V → “are”
NAME 5
SID
Fill in the remaining rows below to illustrate each next step in the shiftreduce parsing.
[ * Students at PSU are very intelligent and hardworking ]
NAME 6
SID
5. Machine learning, perceptrons, and neural nets (8 parts, 20 points total)
5a. How can a linear regression be used as a classifier (2.5 points) ?
5b. How is an understanding of linear regression used as a classifier, or of classification with
logistic regression, related to a perceptron (2.5 points) ?
5c. In a feedforward network of perceptrons, how are the neural units connected (2.5 points) ?
5dh. In the unlabeled picture of a percepton shown below, fill in the content for 5d. 5h (2.5
points each of d through h) .