DOC PREVIEW
Berkeley COMPSCI 188 - Final Exam

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

NAME: SID#: Section: 1CS 188 Introduction to AIFall 2005 Stuart Russell FinalYou have 2 hours and 50 minutes. The exam is open-book, open-notes. 100 points total. Panic not.Mark your answers ON THE EXAM ITSELF. Write your name, SID, and section number at the top of each page.For true/false questions, CIRCLE True OR False.For multiple-choice questions, CIRCLE ALL CORRECT CHOICES (in some cases, there may be more than one).If you are not sure of your answer you may wish to provide a brief explanation.For official use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Q. 7 Total/12 /15 /16 /15 /8 /16 /18 /1001. (12 pts.) Some Easy Questions to Start With(a) (2) True/False: Suppose that variables X1, X2, . . . , Xkhave no parents in a given Bayes net that contains nvariables in all, where n > k. Then the Bayes net asserts that P(X1, X2, . . . , Xk) = P(X1)P(X2) · · · P(Xk).(b) (2) True/False: In a fully observable, turn-taking, zero-sum game between two perfectly rational players,it does not help the first player to know what move the second player will make.(c) (2) True/False: For any propositional sentences α, β, γ, if at least one of [α |= γ] and [β |= γ] holds then(α ∧ β) |= γ(d) (2) True/False: For any propositional sentences α, β, γ, if (α ∧ β) |= γ then at least one of [α |= γ] and[β |= γ] holds(e) (2) True/False: If C1and C2are two first-order clauses that have been standardized apart, then no literalin C1is identical to any literal in C2.(f) (2) True/False: New lexical categories (such as Noun, Verb, Preposition, etc.) are frequently added toEnglish.NAME: SID#: Section: 22. (15 pts.) Searchn vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must bemoved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n − i + 1, n).On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but ifa vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannotoccupy the same square.(a) (4) The size of the state space is roughly(i) n2(ii) n3(iii) n2n(iv) nn2(b) (3) The branching factor is roughly(i) 5 (ii) 5n (iii) 5n(c) (2) Suppose that vehicle i is at (xi, yi); write a nontrivial admissible heuristic hifor the number of movesit will require to get to its goal location (n − i + 1, n), assuming there are no other vehicles on the grid.(d) (2) Which of the following heuristics are admissible for the problem of moving all n vehicles to theirdestinations?(i)Pni = 1hi(ii) max{h1, . . . , hn} (iii) min{h1, . . . , hn} (iv) None of these(e) (4) Explain your answer to part (d).NAME: SID#: Section: 33. (16 pts.) Propositional LogicSuppose an agent inhabits a world with two states, S and ¬S, can do exactly one of two actions, a and b.Action a does nothing and action b flips from one state to the other. Let Stbe the proposition that the agentis in state S at time t, and let atbe the proposition that the agent does action a at time t (similarly for bt).(a) (4) Write a successor-state axiom for St+1(b) (4) Convert the sentence in (a) into CNF.(c) (8) Show a resolution refutation proof that if the agent is in ¬S at time t and does a it will still be in ¬Sat time t + 1.NAME: SID#: Section: 44. (15 pts.) Pruning in search treesIn the following, a “max” tree consists only of max nodes, whereas an “expectimax” tree consists of a maxnode at the root with alternating layers of chance and max nodes. At chance nodes, all outcome probabilitiesare non-zero. The goal is to find the value of the root with a bounded-depth search.(a) (2) Assuming that leaf values are finite but unbounded, is pruning (as in alpha-beta) ever possible in amax tree? Give an example, or explain why not.(b) (2) Is pruning ever possible in an expectimax tree under the same conditions? Give an example, or explainwhy not.(c) (2) If leaf values are constrained to be nonnegative, is pruning ever possible in a max tree? Give anexample, or explain why not.(d) (2) If leaf values are constrained to be nonnegative, is pruning ever possible in an expectimax tree? Givean example, or explain why not.NAME: SID#: Section: 5(e) (2) If leaf values are constrained to be in the range [0, 1], is pruning ever possible in a max tree? Give anexample, or explain why not.(f) (2) If leaf values are constrained to be in the range [0, 1], is pruning ever possible in an expectimax tree?Give an example (qualitatively different from your example in (e), if any), or explain why not.(g) (3) Consider the the outcomes of a chance node in an expectimax tree. Which of the following evaluationorders is most likely to yield pruning opportunities?(i) Lowest probability first (ii) Highest probability first (iii) Doesn’t make any difference5. (8 pts.) MDPsConsider the world in Q.3 as an MDP, with R(S) = 3, R(¬S) = 2, and γ = 0.5. Complete the columns of thefollowing table to perform policy iteration to find the optimal policy.π0Vπ0π1Vπ1π2S a¬S aNAME: SID#: Section: 6BIMGJP(B).9.1P(M)B M P(I)T T .9T F .5F T .5F F .1TFG P(J).9.0TTFFTTFFTFTFTFTFTTTTFFFF.9B I M P(G).0.0.0.0.8.2.1Fig. 1: A simple Bayes net with Boolean variables B = BrokeElectionLaw, I = Indicted,M = P oliticallyM otivatedP rosecutor, G = F oundGuilty, J = J ailed.6. (16 pts.) Probabilistic inferenceConsider the Bayes net shown in Fig. 1.(a) (3) 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) = P(J|G, I)(iii) P(M |G, B, I) = P(M |G, B, I, J)(b) (2) Calculate the value of P (b, i, ¬m, g, j).(c) (4) Calculate the probability that someone goes to jail given that they broke the law, have been indicted,and face a politically motivated prosecutor.(d) (2) A context-specific independence has the following form: X is conditionally independent of Y given Zin context C = c if P(X|Y, Z, C = c) = P(X|Z, C = c). In addition to the usual conditional independencesgiven by the graph structure, what context-specific independences exist in the Bayes net in Fig. 1?NAME: SID#: Section: 7(e) (5) Suppose we want to add the variable P = P residentialP ardon to the network; draw the new networkand briefly explain any links you add.NAME: SID#: Section: 87. (18 pts.) Language and statistical learningA probabilistic context-free grammar (PCFG) is a context-free grammar augmented with a


View Full Document

Berkeley COMPSCI 188 - Final Exam

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?