Student ID: Last Name: First Name: USC email:
Instructions:
samplequestionsf14–2 #1 1 of 10
Practice Midterm Examination
CSCI 561 FALL2014: Artificial Intelligence
Rubric is not provided. You are welcome to
discuss your answers to this exam on Piazza, and
to all together come up with an agreed solution. We will
help you if needed. Please elaborate this as “the students’ answer” or followup discussion on piazza topic @140
54E37446-2E8D-4C38-9C24-F7F9F6608424
1. Date:9/29/2014from5:00pm–6:20pm
2. Maximumcredits/pointsforthismidterm:100points.
3. Credits/pointsforeachquestionisindicatedinthebrackets[]beforethequestion.
4. Nobooks(oranyothermaterial)areallowed.
5. Attachextrasheets(availableuponrequest)ifrequired(writefullnameoneachextra sheet).
6. Writedownname,studentIDanduscemailaddress.
7. Noquestionsduringtheexam.
8. Bebrief:afewwordsareoftenenoughiftheyarepreciseandusethecorrect vocabulary studied in class.
9. Whenfinishedraisecompletedexamsheetsuntilapproachedbyproctor.
10.Adhere to the Academic Integrity code.
1 of 9
(i) [1%]
(ii) [1%] (iii) [1%]
(iv) [1%]
(v) [1%] (vi) [1%] (vii) [1%] (viii) [1%] (ix) [1%]
(x) [1%]
(xi) [1%] (xii) [1%] (xiii) [1%]
(xiv) [1%] (xv) [1%]
___ The Turing test defines the conditions under which a machine can be said to be “intelligent”.
___ My office is not an accessible environment.
___ A contingency problem involves a nondeterministic and accessible environment.
___ During search, one usually applies the goal test onto newly expanded children, before queuing-up these children.
___ If the cost of applying an operator once is always 1, then BFS is optimal. ___ A* is an admissible algorithm.
___ DFS is faster than BFS.
___ DFS has lower asymptotic space complexity than BFS.
___ When using the correct temperature decrease schedule, simulated annealing is guaranteed to find the global optimum in finite time.
___ Alpha-beta pruning accelerates game playing at the cost of being an approximation to full minimax.
___ Genetic algorithms use a step called “failover”. ___ Hill-climbing is an entirely deterministic algorithm.
___ The exact evaluation function values do not affect minimax decision as long as the ordering of these values is maintained.
___ A perfectly rational backgammon-playing agent never loses
___ Hill climbing search is best used for problem domains with densely packed goals
7ABA854E-9904-45D2-BB51-941962CB1348
SampleQuestionsF14 #1 2 of 10
1. [15%] General AI knowledge.
For each of the statements below, write T if the statement is always and unconditionally true, and write F if it is always false, sometimes false, or just does not make sense:
2 of 9
SampleQuestionsF14 #1 3 of 10
2. [15%] Search Algorithms Concepts.
Let’s formalize the traveling salesman problem (TSP) as a search problem. Remember that the goal in this problem is to find the shortest possible route that visits every city on a map exactly once, as exemplified below:
Suboptimal solution (long path) Optimal solution
Assume that we have n cities forming a set C={c1, …, cn}. Also assume that you can travel from any city in that set to any other city, and that the distance between any two cities ci and cj is given by d(ci, cj). Please be concise but precise in your answers. Define:
(a) [5%] A suitable representation for states:
3 of 9
D00A53F3-4825-4484-AAB2-A53A8C6081B1
D8EBDEEE-B47F-46B7-8CE2-BFABEAA43431
SampleQuestionsF14 #1 4 of 10
(b) [2%] The initial state of the problem:
(c) [3%] A good goal test to use in this problem:
(d) [3%] Good operators to use for search:
(e) [2%] Which search algorithm would be the most appropriate to use here if we want to ensure that the shortest possible path is found?
4 of 9
SampleQuestionsF14 #1 5 of 10
3. [30%] Comparing Search Strategies
Consider the search space on the following page, where S is the start node and G1, G2 and G3 satisfy the goal test. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes.
For each of the following search strategies (next page), indicate which goal state is reached (if any) and list, in order, all the states of the nodes popped off of the OPEN queue. When all else is equal, nodes should be removed from OPEN in alphabetical order.
You should not expand nodes with states that have already been visited. Note how the arcs in the figure are oriented, which means that you can only go from one state to another if the arrow points from the first to the second. For example, you can go from S to A (i.e., A is a successor of S) but not from A to S (i.e., S is not a successor of A).
(a) [10%] Depth-first search
Goal state reached: _______ States popped off OPEN: _____________________________
(b) [10%] Uniform cost Search
Goal state reached: _______ States popped off OPEN: _____________________________
(c) [10%] A* Search
Goal state reached: _______ States popped off OPEN: _____________________________
5 of 9
5557787A-F847-4EA3-A09D-65E41348DAC0
B96DBB71-B981-42E1-A5FF-0CD1954FD08F
SampleQuestionsF14 #1 6 of 10
6 of 9
4. [10%] Game Playing.
Consider the following game tree in which the evaluation function values are shown below each leaf node. Assume that the root node corresponds to the minimizing player. Assume that the search always visits children left-to-right.
(a) [4%] Compute the backed-up values computed by the minimax algorithm. Show your answer by writing values at the appropriate nodes in the above tree.
(b) [6%] Which nodes will not be examined by the alpha-beta pruning algorithm? Mark them on the tree above.
AEE22AEA-EA53-409C-B405-3DE9CF0B5412
SampleQuestionsF14 #1 7 of 10
7 of 9
0522238E-236E-46FA-A09E-4D9747A04793
SampleQuestionsF14 #1 8 of 10
5. [10%] Constraint Satisfaction
Given the constraint graph for the 4-queens problem for the board below. (a) [1%] List the variable names
(b) [1%] What do the variables represent?
(c) [1%] What are the domain values?
(d) [1%] How do the constraints (edges) affect the variables for this problem? (e) [1%] How many binary constraints are there?
!!!!!!!!!!!!!!!!!!!!!!!!!
(f) Draw the constraint graph again after performing Arc Consistency to solve this 4 queens board, given the first queen’s position is square 1.
8 of 9
SampleQuestionsF14 #1 9 of 10
6. [20%] AI Applications.
(a) [5%] Which AI application has a discrete, static environment?
a. RobocupSoccerrobots
b. GoogleSelf-drivingcar
c. IBM’s Deep Blue
d. Alloftheabove
e. Noneoftheabove
(b) [5%] Virtual agents Ada and Grace have this ability in common with IBM Watson?
a. Text-to-SpeechSynthesis
b. Naturallanguageprocessing
c. Knowledge representation
d. Alloftheabove
e. Noneoftheabove
(c) [5%] In building a poker-playing robot, what is most important?
a. ItshouldpasstheTuringTest
b. Itshouldbeabletoholdthecards
c. It should be able to reason in a dynamic, continuous environment
d. Alloftheabove
e. Noneoftheabove
(d) [5%] An admissible heuristic for the Google Maps could be?
a. Straight-linedistance
b. Costoftransportation
c. Time during rush hour traffic
d. Alloftheabove
e. Noneoftheabove
9 of 9
647688A1-BE7A-49FD-9F60-EADD516BC195
B955AB75-25A1-4067-A1AC-3A6FF574A89F
SampleQuestionsF14 #1 10 of 10