COMP 380: Midterm Examination Fall 2020
I commit to abiding by UFV’s policies on cheating and plagiarism.
(indicate your agreement by writing your name and student number below) Student name:
Student number:
● All answers must be written in your own words.
● Pasting a quote from the textbook does not count as an answer.
● Submitting someone else’s work as your own is plagiarism and can result in failure in the
exam or failure in the course.
● You are not permitted to discuss the exam with other students during the exam period.
Section A (multiple choice and true/false) [25 points] is on Blackboard.
Section
Possible Points
Points
B
20
C
5
D
5
Total
30
Write your answers in this doc file and submit via Blackboard. Remember to save your file often.
Remember to complete the multiple-choice section on Blackboard.
Section B. Short Answer (2-3 sentences each)
1. [2 points] Give two examples of the limitations of the STRIPS representation for planning, i.e. things it
cannot represent or cannot easily represent. a.
b.
2. [2 points]
a. In what sense is branch-and-bound search similar to A* search?
b. In what sense is branch-and-bound search similar to depth-first search?
3. [2 points] How does A* search extend best-first search?
4. [2 points] If we have a search problem that does not involve costs, can we still use a heuristic function with
A* in order to find the optimal solution? Explain your answer.
5. [3 points] Define a plateau. Why are plateaus a problem for local search applied to constraint satisfaction problems?
6. [2 points] What are the two key weaknesses of Stochastic Local Search?
A. B.
7. [2 points] If we unroll a CSP planning problem to horizon k and do not find a solution, is there any point in unrolling it to a larger time horizon and trying again? Explain why or why not.
8. [3 points] If we have two admissible heuristics h1 and h2, would it be better to use min(h1, h2) or max(h1, h2) as a heuristic with A* search? Briefly explain your answer.
9. [2 points] How many states can be represented by four variables, each of which can take five values?
Section C. Arc Consistency
Consider the following constraint network.
10. [3 points] If the variables A, B and C each have the domain {1,2,3,4} before arc consistency is run, indicate what their domains will be after arc consistency has finished:
A={} B={ } C={}
11. [2 points] If we have just considered the edge
Section D. Optimality of A*
Assume that we are running A* search on a problem and we find path p to a goal. In the lecture and text, we proved mathematically that, if we are using an admissible heuristic, there is no other path that is shorter than p. In other words, if path p’ is still on the frontier, and p” is a path to the goal that extends p’, path p will always be less than (or equal to) p”. This is called proving the optimality of A*.
12. [5 points] Explain why we cannot prove the optimality of A* if the heuristic is not admissible. Be as specific and detailed as possible, referring to the proof in your answer.
Remember to complete the multiple-choice section on Blackboard.